首页 > 代码库 > [leetcode]_Balanced Binary Tree

[leetcode]_Balanced Binary Tree

2024-07-04 14:13:06   228人阅读

第四道树题，逐渐能写递归了。虽然最后AC的代码还是看了网络，但是距离成功攻克此类问题仅一步之遥。

题目：一棵树，判断是否为AVL。(AVL条件：树上任意一点的左右子树的高度差<=1)

思路：树依旧用递归的思想。

解题历程：

1、凭感觉，依葫芦画瓢之前看的递归程序。“判断一颗树是否AVL，如果该node != null ，则递归地判断其 leftSubTree 和 rightSubTree是否为AVL。（这个地方错了，在第三块代码中反映出来，不是node != null ，应该是如果node结点是平衡的 ， 则递归判断其左右子树是否平衡）

public boolean isBalanced(TreeNode root) {
       if(root == null) return true;
       
       else return isBalanced(root.left) && isBalanced(root.right);
    }

我只写到了这步，但是但是，这个递归程序只能返回true啊，任意一棵树都会返回true。华丽丽地WA。

 

2、思考是哪里错了，是否直接用isBalanced(root.left)和isBalanced(root.right)不对呢？是否应该在求高度时用递归呢。

一个结点的高度 = MAX(该结点左子树高度 ， 该结点右子树高度) + 1;如果左右子树高度差绝对值<= 1 ,返回true，反之。

至此，我修改了程序：

public boolean isBalanced(TreeNode root) {
       if(root == null) return true;
       else return Math.abs(calHeight(root.left) - calHeight(root.right)) <= 1 ? true : false ;
      
   }
   
public int calHeight(TreeNode node) {
       if(node == null) return 0;
       else  return Math.max(calHeight(node.left) , calHeight(node.right)) + 1;
    }

Submit。依旧WA。问题出在isBalance()中计算高度，我只计算了根节点root的左右子树的高度，左右子树中任一结点的高度差是否大于1无从得知。

 

3、上述代码的修改意见，应该就是加上各个结点的高度差判断，但是，我不会写了。%>_<%。网络上的AC代码：

public boolean isBalanced(TreeNode root) {
       if(root == null) return true;
      
       if(Math.abs(calHeight(root.left) - calHeight(root.right)) > 1 ) return false;
       
       else return isBalanced(root.left) && isBalanced(root.right);
    }
   
public int calHeight(TreeNode node) {
       if(node == null) return 0;
       else  return Math.max(calHeight(node.left) , calHeight(node.right)) + 1;
    }

惊奇地发现，就是我1，2版本代码的并集。再理下思路：

当一棵树root结点为Null时，该树为AVL。

判断该root结点是否平衡，如果不平衡，则直接返回false;如果平衡，则递归地判断该root结点的左右子树是否平衡，如果左右子树都平衡，才返回true。


联系
我们