剑指 Offer 55 - I. 二叉树的深度 & 55 - II. 平衡二叉树

I题目描述:

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

解析：

1.终止条件：当 root为空，说明已越过叶节点，因此返回深度0
2.递推工作：本质上是对树做后序遍历。
计算节点 root的左子树的深度，即调用 maxDepth(root.left)；
计算节点 root的右子树的深度，即调用 maxDepth(root.right)；
3.返回值：返回此树的深度，即 max(maxDepth(root.left), maxDepth(root.right)) + 1。

Java:

public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

JavaScript:

var maxDepth = function(root) {
    if(root === null) {
        return 0;
    }
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

II题目描述:

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

解析：

库函数加平衡二叉树判断
1.首先判断根节点是否为空，若为空，直接返回true
2.定义左右子树的高度（调用maxDepth函数）
判断是否为平衡二叉树，若不为平衡二叉树，则返回false
若为平衡二叉树，则继续遍历左右子树的节点
3.maxDepth函数为二叉树的高度

Java:

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

JavaScript:

var isBalanced = function(root) {
    if(root === null) {
        return true;
    }
    let left = MaxDepth(root.left);
    let right = MaxDepth(root.right);
    if((left - right) > 1 || (left - right) < -1) {
        return false;
    } else {
        return isBalanced(root.left) && isBalanced(root.right);
    }

    function MaxDepth(root) {
        if(root === null) {
            return 0;
        }
        return Math.max(MaxDepth(root.left), MaxDepth(root.right)) + 1;
    }
};