【剑指】判断一个树是不是平衡二叉树

青旅半醒 2023-07-01 09:00 3阅读 0赞

如题；  
思路：根据根节点的左右子树的深度是否差值是在1内，且他的以左右子树为根节点的所有树都是平衡二叉树  
结合之前剑指的求二叉树深度来做

代码：

class Solution { 
    public://还得是二叉搜索树和平衡的
        bool IsBalanced_Solution(TreeNode* pRoot) { 
            if(!pRoot)    return true;
            int left=getdepth(pRoot->left);
            int right=getdepth(pRoot->right);
            if(abs(left-right)>1)
                return false;
            else
                return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
            
        }
        
        private:    
        int getdepth(TreeNode* pnode)
        { 
            if(!pnode)
                return 0;
            return 1+max(getdepth(pnode->left), getdepth(pnode->right));
        }
            
        
    };

但是这样的方式时间复杂度是O（N\*N）而且同一个节点要遍历两次。这是前序遍历的结果。  
我们可以选择在后序遍历的方式，这样就是遍历一遍方式，并且注意的是通过引用来传递深度的值。

bool IsBalanced_Solution(TreeNode* pRoot,int &depth){ 
    	if(pRoot==nulllptr)
    		{ 
    		depth=0;
    		return true;
    		}
    	int left=0;
    	int right =0;
    	if(IsBalanced_Solution(pRoot->left,left)&&IsBalanced_Solution(pRoot->right,right)){ 
    	if(abs(left-right)>1)
    		return false;
    	depth=1+max(left,right);
    		return true;
    	}
    	return false;
    }

//后序遍历，只计算一次。

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关判断一棵树是不是二叉平衡树

转载代码： public class Solution { private boolean isBalanced = false;//最后的返回值

末蓝、/ 2023年07月24日 11:56/ 0 赞/ 107 阅读

相关判断一个二叉树是否是平衡二叉树

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例 1: 给定二叉树 \[3,9,20,null,null,15,7\]

比眉伴天荒/ 2023年07月24日 08:57/ 0 赞/ 14 阅读

相关【剑指】49，平衡二叉树判断

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。思路; 首先确认平衡二叉树定义，首先是二叉树，其次是每个节点的左右子树的高度差的绝对值要小于等于一，并且该

港控/mmm°/ 2023年07月12日 14:19/ 0 赞/ 62 阅读

相关【剑指】判断一个树是不是平衡二叉树

如题；思路：根据根节点的左右子树的深度是否差值是在1内，且他的以左右子树为根节点的所有树都是平衡二叉树结合之前剑指的求二叉树深度来做代码： class

青旅半醒/ 2023年07月01日 09:00/ 0 赞/ 4 阅读

相关【算法】判断二叉树是否是平衡二叉树

问题：判断一个二叉树是否是平衡二叉树。分析：平衡二叉树要求左子树和右子树的高度相差为1，且左右子树都是平衡二叉树。递归可以很好的解决这个问题。但是首先要求树的深度。代码

迈不过友情╰/ 2022年08月09日 05:08/ 0 赞/ 335 阅读

相关剑指offer：判断是否是平衡二叉树

这种写法，效率比较高，每一个节点只访问一次。 struct TreeNode { int val; struct TreeNode left;

╰半夏微凉°/ 2022年08月09日 02:18/ 0 赞/ 236 阅读

相关判断二叉树是不是平衡二叉树

输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。例如下图中的二叉树就是一棵平衡二叉树： ![C

ゞ浴缸里的玫瑰/ 2022年08月02日 04:49/ 0 赞/ 337 阅读

相关判断二叉树是否是平衡树

面试题39：输入一颗二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中节点的左右子树的深度相差不超过1，那么它就是一颗平衡二叉树 //判断二叉树是不是平衡树

「爱情、让人受尽委屈。」/ 2022年06月17日 07:08/ 0 赞/ 336 阅读

相关判断二叉树是否是平衡二叉树

平衡二叉搜索树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。思路：如

àì夳堔傛蜴生んèń/ 2022年04月18日 01:47/ 0 赞/ 386 阅读

相关【数据结构】（平衡二叉树）判断二叉树是否是平衡二叉树

> 算法思想：判断一棵树是否为平衡二叉树可以采取高度差的递归方式来判断这个方法比较简单但是复杂度较高（因为高度被重复计算了很多次）O（nlogn） //递归求高度

短命女/ 2021年10月29日 14:50/ 0 赞/ 489 阅读