题目一

题目描述

二叉树的深度

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

二叉树的节点定义如下：

测试用例

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

解题思路

递归思路

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

参考解题

/** * 二叉树的深度 * */
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。

参考解题

/** * 二叉平衡树 * */
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;
        }

    }

}

题目考点

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