精华内容
下载资源
问答
  • 判断一棵二叉树是否为平衡树: 实现一个函数,检查二叉树是否平衡,平衡的定义如下,对于树中的任意 一个结点,其两颗子树的高度差不超过1。 给定指向树根结点的指针TreeNode* root,请返回一个bool,代表这棵树是否...

    判断一棵二叉树是否为平衡二叉树:

    实现一个函数,检查二叉树是否平衡,平衡的定义如下,对于树中的任意 一个结点,其两颗子树的高度差不超过1。

    给定指向树根结点的指针TreeNode* root,请返回一个bool,代表这棵树是否平衡。

    import java.util.*;
     
    /*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }*/
    public class Balance {
         public boolean isBalance(TreeNode root) {
            //根结点为空,则这个二叉树为平衡二叉树
            if(root==null){  
                return true;
            }
            int left=getLength(root.left);   //左子树的高度
            int right=getLength(root.right); //右子树的高度
            if(Math.abs(left-right)<=1){
                return isBalance(root.left)&&isBalance(root.right);
            }else{
                return false; //只要有一个结点不平衡,则返回false
            }
     
        }
     
        //计算二叉树的高度
        private int getLength(TreeNode root) {
            if(root==null){
                return 0;
            }
            int l=getLength(root.left);  //左子树的高度
            int r=getLength(root.right); //右子树的高度
            if(l>r){
                return l+1;  //二叉树的高度为左右子树高度最大值加1
            }else{
                return r+1;
            }
        }
    }
    
    展开全文
  • 左神算法基础class4—题目6判断一棵二叉树是否是平衡二叉树1.题目:判断一棵二叉树是否是平衡二叉树2.分析(1)平衡二叉树的概念(2)二叉树题解套路3.核心代码(1)树的建立(2)设计递归返回结构(3)递归过程(4...

    1.题目:判断一棵二叉树是否是平衡二叉树

    2.分析

    (1)平衡二叉树的概念

    平衡二叉树指对于任意节点,其左右节点高度差不超过1。满二叉树一定是平衡二叉树,平衡二叉树不一定是满二叉树。
    在这里插入图片描述
    对于4,5节点左右都为空,高度为0,差为0符合;
    对于2节点,左高为0,右高为1,差为1符合;
    对于3节点,左高为1,右高为0,差为1符合;
    对于1节点,左高为2,右高为2,差为0符合;
    所以上述树为平衡二叉树。
    在这里插入图片描述
    增加节点6后,对于3节点,左高为2,右高为0,不符合。

    (2)二叉树题解套路

    (可阅读树形dp问题)
    -使用递归函数来求解二叉树某些问题,对于本题,所有节点都是平衡的,那么整颗树平衡。

    • 1
      对于当前节点x需要的信息如下(列出可能性):
      ①左平衡否:左不平衡则整颗树不平衡
      ②右平衡否:右不平衡则整颗树不平衡
      在都平衡前提下再判断高度差,需要左右子树的高度信息:
      ③左高
      ④右高
    • 2
      设计递归返回结构:递归中需要平衡信息和高度信息
    • 3
      写代码

    3.核心代码

    (1)树的建立

    //树结构
    class Tree
    {
    public:
    	int val;
    	Tree* left;
    	Tree* right;
    	Tree(int num)
    	{
    		this->val = num;
    		right = NULL;
    		left = NULL;
    	}
    };
    
    //main函数中
    	Tree *head = new Tree(1);
    	head->left = new Tree(2);
    	head->left->right = new Tree(4);
    	head->right = new Tree(3);
    	head->right->left = new Tree(5);
    	head->right->left->right= new Tree(6);
    

    (2)设计递归返回结构

    需要高度信息和是否平衡的信息(true,false)

    //返回信息类
    class returnData
    {
    public:
    	int h;		//高度
    	bool isB;	//平衡否
    	returnData(bool isB,int h)//构造函数
    	{
    		this->h = h;
    		this->isB = isB;
    	}
    };
    

    (3)递归过程

    思路:把整个过程视为一个黑盒,假设可以得到左树信息,再得到右树信息,对两棵子树求高度差并判断,最后向上返回。
    对整个过程补充一些细节,①一开始时如果当前节点为空,返回平衡true、高度为0;②得到左树信息后如果子树平衡信息为false则直接返回false,右树也是同理;③最后如果高度差不大于1时,说明当前节点平衡,返回给其父节点的信息是平衡true,高度为当前节点高度最大值再加上当前节点(+1)

    returnData* process(Tree* head)
    {
    	if(head == NULL)//空树平衡,高度为0
    		return new returnData(true,0);
    	
    	returnData* leftData = process(head->left);//假设可以在左树收到信息	
    	if(!leftData->isB)//已经不平衡直接返回
    		return new returnData(false,0);
    	
    	returnData* rightData = process(head->right);//假设可以在右树收到信息
    	if(!rightData->isB)//已经不平衡直接返回
    		return new returnData(false,0);
    
    	//在都平衡时求高度差
    	if(abs(leftData->h - rightData->h) > 1)
    		return new returnData(false,0);
    	
    	//返回左右树最高高度加1
    	return new returnData(true,max(leftData->h , rightData->h) + 1);
    }
    

    (4)判断函数

    我们只需要递归过程中平衡的信息

    bool isBalance(Tree* head)
    {
    	return process(head)->isB;
    }
    

    4.完整代码

    #include<iostream>
    using namespace std;
    
    //树结构
    class Tree
    {
    public:
    	int val;
    	Tree* left;
    	Tree* right;
    	Tree(int num)
    	{
    		this->val = num;
    		right = NULL;
    		left = NULL;
    	}
    };
    
    //需要返回的信息
    class returnData
    {
    public:
    	int h;		//高度
    	bool isB;	//平衡否
    	returnData(bool isB,int h)//构造函数
    	{
    		this->h = h;
    		this->isB = isB;
    	}
    };
    
    //递归
    returnData* process(Tree* head)
    {
    	if(head == NULL)//空树平衡,高度为0
    		return new returnData(true,0);
    	
    	returnData* leftData = process(head->left);//假设可以在左树收到信息	
    	if(!leftData->isB)//已经不平衡直接返回
    		return new returnData(false,0);
    	
    	returnData* rightData = process(head->right);//假设可以在右树收到信息
    	if(!rightData->isB)//已经不平衡直接返回
    		return new returnData(false,0);
    
    	//在都平衡时求高度差
    	if(abs(leftData->h - rightData->h) > 1)
    		return new returnData(false,0);
    	
    	//返回左右树最高高度加1
    	return new returnData(true,max(leftData->h , rightData->h) + 1);
    }
    
    //判断函数
    bool isBalance(Tree* head)
    {
    	return process(head)->isB;
    }
    
    int main()
    {
    	Tree *head = new Tree(1);
    	head->left = new Tree(2);
    	head->left->right = new Tree(4);
    	head->right = new Tree(3);
    	head->right->left = new Tree(5);
    	head->right->left->right= new Tree(6);
    
    	cout<<isBalance(head);
    	
    	system("pause");
    	return 0;
    }
    
    展开全文
  • 对于该树的任意子树,其最大距离的求解分为以下三种情况: 该树的最大距离是左子树的最大距离。 该树的最大距离是右子树的最大距离。 该树的最大距离是从左子树的最深的那个结点经过该树的头结点走到右子树的最深的...

    进阶5 01.04.16
    在这里插入图片描述
    注意是最短路径,不能是3走到6、再从6走到3、再从3走到6,然后在去目标节点

    例子:
    这棵树最远距离是 6到10。
    沿途8个节点
    在这里插入图片描述

    对于该树的任意子树,其最大距离的求解分为以下三种情况:

    • 该树的最大距离是左子树的最大距离。
    • 该树的最大距离是右子树的最大距离。
    • 该树的最大距离是从左子树的最深的那个结点经过该树的头结点走到右子树的最深的那个结点。

    要从子树收集的信息:

    • 子树的最大距离
    • 子树的深度
      return type
      在这里插入图片描述
      递归过程:
      在这里插入图片描述
      解析:
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    展开全文
  • 二叉树

    2019-10-04 06:35:12
    二叉树 二叉树的基本概念 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree) ...0)性质3:对于任意一棵二叉树,如果其叶结点数为N0,而度...

    二叉树

    二叉树的基本概念

    二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)

    二叉树的性质(特性)

    性质1: 在二叉树的第i层上至多有2^(i-1)个结点(i>0)
    性质2: 深度为k的二叉树至多有2^k - 1个结点(k>0)
    性质3: 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;
    性质4:具有n个结点的完全二叉树的深度必为 log2(n+1)
    性质5:对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为i/2(i=1 时为根,除外)

    (1)完全二叉树——若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。完全二叉树

    (2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
    满二叉树

    二叉树的节点表示以及树的创建

    通过使用Node类中定义三个属性,分别为elem本身的值,还有lchild左孩子和rchild右孩子

    class Node(object):
        """节点类"""
        def __init__(self, elem=-1, lchild=None, rchild=None):
            self.elem = elem
            self.lchild = lchild
            self.rchild = rchild
    

    树的创建,创建一个树的类,并给一个root根节点,一开始为空,随后添加节点

    class Tree(object):
        """树类"""
        def __init__(self, root=None):
            self.root = root
    
        def add(self, elem):
            """为树添加节点"""
            node = Node(elem)
            #如果树是空的,则对根节点赋值
            if self.root == None:
                self.root = node
            else:
                queue = []
                queue.append(self.root)
                #对已有的节点进行层次遍历
                while queue:
                    #弹出队列的第一个元素
                    cur = queue.pop(0)
                    if cur.lchild == None:
                        cur.lchild = node
                        return
                    elif cur.rchild == None:
                        cur.rchild = node
                        return
                    else:
                        #如果左右子树都不为空,加入队列继续判断
                        queue.append(cur.lchild)
                        queue.append(cur.rchild)

     

     

    转载于:https://www.cnblogs.com/amou/p/9058395.html

    展开全文
  • 对于任意一棵二叉树,如果2度的节点数有n2个,则叶子数n0必定为n2+1(n0=n2+1) (1) 我们假设有二叉树的枝有B个,如果从下往上思考,可以看做是每个节点都有一个枝与之对应,那么可以有B = n - 1成立,之所以有减一是...
  • 思路:对于二叉树来说遍历的时候最好是利用递归的方法 1、首先设置标志位result = false,因为一旦匹配成功result就设为true,剩下的代码不会执行,如果匹配不成功,默认返回false。 2、递归思想,如果根节点相同则...
  • 二叉树 二叉树的基本概念 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right ...0)性质3: 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总...
  • 二叉树基础知识

    2018-11-24 17:45:00
    对于任意一棵二叉树,如果其叶节点数为,度为2的结点数为,则一定满足。 具有个结点的完全二叉树的深度为。 对于任意一棵具有个结点的完全二叉树,对于任意一个结点(编号为),有: 如果,则结点为根 如果,...
  • Python 二叉树

    2020-04-23 00:28:17
    一、二叉树的基本概念 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree...性质3: 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为...
  • 二叉树遍历

    热门讨论 2018-04-20 09:58:45
    一、概念: 二叉树:是n(n≥0)个结点的有限集合,它或者是空树(n=0),或者是由一个根结点及两棵不相交的且分别称为左、右子树的二叉树所组成。 结点的度:结点子树的个数 ...(3) 对于任意一棵二叉树,若其...
  • 24 二叉树

    2019-08-21 15:25:23
    二叉树 是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)...性质3: 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1; 性质...
  • 7.2 二叉树

    2018-07-05 15:51:00
    (1)二叉树的基本概念:  二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree) ...0) 性质3:对于任意一棵二叉树,如果其叶结点数为N...
  • 二叉树 二叉树的基本概念 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right ...0)性质3:对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总...
  • 概述二叉树,是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右...对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1; 具有n个结点的完全二叉树的深度为
  • 基本概念二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”...0)性质3: 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;性质4:具有n个结...
  • 二叉树 二叉树的基本概念 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right ...0)性质3:对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总...
  • python 二叉树

    2018-03-15 17:50:10
    概念 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree...性质3: 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 698
精华内容 279
关键字:

对于任意一棵二叉树