二叉树的深度.md

题目一

题目描述

二叉树的深度

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

二叉树的节点定义如下：

测试用例

• 功能测试（输入普通的二叉树；二叉树中所有节点都没有左/右子树）
• 特殊输入测试（二叉树只有一个节点；二叉树的头节点为空指针）

解题思路

递归思路

一个树的深度可以理解为左、右子树深度的最大值加1。

自己解题

完全遍历，垃圾。

参考解题

/**
 * 二叉树的深度
 *
 * @Author rex
 * 2018/9/11
 */
public class Solution1 {
    /**
     * 递归
     * @param root
     * @return
     */
    public int treeDepth(BinaryTreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = treeDepth(root.left);
        int right = treeDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

题目二

平衡二叉树

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

测试用例

• 功能测试（输入普通的二叉树；不是平衡的二叉树；二叉树中所有节点都没有左/右子树）
• 特殊输入测试（二叉树只有一个节点；二叉树的头节点为空指针）

解题思路

利用树的深度来判断

自己解题，虽然更为清晰，但是重复遍历太多。

参考解题思想是树的后序遍历（从下到上）。在每个节点记录它的深度，如果不平衡，则记录该节点的深度为-1。

自己解题

/**
 * 平衡二叉树
 *
 * @Author rex
 * 2018/9/11
 */
public class Solution2 {
    /**
     * 自己解题
     * 太多重复遍历 19ms
     * @param root
     * @return
     */
    public boolean isBalanced_Solution(BinaryTreeNode root) {
        if (root == null) {
            return true;
        }
        int left = treeDepth(root.left);
        int right = treeDepth(root.right);
        if (Math.abs(left-right) > 1) {
            return false;
        }
        return isBalanced_Solution(root.left) && isBalanced_Solution(root.right);
    }

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

参考解题

/**
 * 二叉平衡树
 *
 * @Author rex
 * 2018/9/11
 */
public class Solution3 {

    /**
     * 判断是否为二叉平衡树
     * @param root
     * @return
     */
    public boolean isBalanced_Solution(BinaryTreeNode root) {
        if (root == null) {
            return true;
        }
        return treeDepth(root) != -1;

    }

    /**
     * 树的深度（后序遍历）
     *
     * @param root
     * @return -1：表示不是二叉平衡树
     */
    public int treeDepth(BinaryTreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = treeDepth(root.left);
        if (left == -1) {
            return -1;
        }
        int right = treeDepth(root.right);
        if (right == -1) {
            return -1;
        }
        if (Math.abs(left - right) > 1) {
            return -1;
        } else {
            return Math.max(left, right) + 1;
        }

    }

}

题目考点

• 考察应聘者对二叉树的理解和编程能力。
• 考察应聘者对新概念（树的深度）的学习能力。
• 考查应聘者的知识迁移能力。