二叉树的深度和平衡二叉树(LeetCode 剑指Offer 55

题目

1. 输入一棵二叉树的根节点，求该树的深度。
2. 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。

二叉树的深度

解析

递归实现。递归的边界条件是节点为null，返回高度为0。否则递归求解左右子树高度，取较大的值加1，为当前节点的高度。

代码

public int maxDepth(TreeNode root) {
    if(null == root){
        return 0;
    }
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    return leftDepth > rightDepth ? (leftDepth + 1) : (rightDepth + 1);
}

判断平衡二叉树

解析

递归实现。在上一题求解树深度的基础上，每个输入的节点，首先节点若为null，则是平衡的。否则，计算左右子树的深度，判断是否符合平衡二叉树要求。如果符合，递归判断左右子树是否符合平衡二叉树要求。

代码

public boolean isBalanced(TreeNode root) {
    //如果当前节点为null，深度为0。
    if(null == root){
        return true;
    }
    //分别求解左右子树高度，然后判断当前节点是否符合平衡二叉树要求
    int left = depth(root.left);
    int right = depth(root.right);
    if(Math.abs(left - right) > 1){
        return false;
    }
    //递归判断左右子树是否符合平衡二叉树要求
    return isBalanced(root.left) && isBalanced(root.right);
}

//如上题，求解节点的深度
private int depth(TreeNode node){
    if(null == node){
        return 0;
    }
    int left = depth(node.left);
    int right = depth(node.right);
    return left > right ? (left + 1) : (right + 1);
}