dfs题目：平衡二叉树(java)

平衡二叉树

• 题目
• 思路
• 开始的error代码（最后一行return的地方有误）
• 修正的代码

题目

思路

用分治的思想，要想看看以root为根节点的二叉树是不是平衡二叉树，得看他的左子树和右子树是不是平衡二叉树，如果左子树和右子树都是平衡的，且root自己是平衡的，就返回true.
看节点的左子树和右子树是否平衡得计算左右子树的深度差，有涉及一个求以root为节点的二叉树的深度的方法，这个方法也是用分治的思想，以root为节点的二叉树的深度=1+max(root左子树的深度，root右子树的深度)。

开始的error代码（最后一行return的地方有误）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //功能：求以root为根的深度
    int getDeep(TreeNode root){

        if(root==null){
            return 0;
        }
        //以root为根的深度=1+以root下一层的深度(较大的子树)
        
        //先求一下root左子树的深度
        int l=getDeep(root.left);
        int r=getDeep(root.right);
        //比较一下，选大的
        if(l>r){
            return 1+l;
        }else{
            return 1+r;
        }
    }
    //函数功能：判断以root为根，判断他的左右子树是否平衡
    public boolean isBalanced(TreeNode root) {

        if(root==null)
        return true;
        //先求root的左子树的深度
        int leftDeep=getDeep(root.left);
        //再求root的右子树的深度
        int rightDeep=getDeep(root.right);
        //比较一下是否左右子树的深度差是否>1
        if(Math.abs(leftDeep-rightDeep)>1){
            return false;
        }
        return true;//错误的地方：没有考虑到root左子树和右子树是否满足平衡
    }
}

修正的代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //功能：求以root为根的深度
    int getDeep(TreeNode root){

        if(root==null){
            return 0;
        }
        //以root为根的深度=1+以root下一层的深度(较大的子树)
        
        //先求一下root左子树的深度
        int l=getDeep(root.left);
        int r=getDeep(root.right);
        //比较一下，选大的
        if(l>r){
            return 1+l;
        }else{
            return 1+r;
        }
    }
    //函数功能：判断以root为根，判断他的左右子树是否平衡
    public boolean isBalanced(TreeNode root) {

        if(root==null)
        return true;
        //先求root的左子树的深度
        int leftDeep=getDeep(root.left);
        //再求root的右子树的深度
        int rightDeep=getDeep(root.right);
        //比较一下是否左右子树的深度差是否>1
        if(Math.abs(leftDeep-rightDeep)>1){
            return false;
        }
        //当root的左子树和右子树是平衡树且root数是平衡树时才是真正的平衡树
        return isBalanced(root.left)&&isBalanced(root.right);
    }
}