二叉树的深度

Easy 原题连接：二叉树的深度

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

示例：

    3
   / \
  9  20
    /  \
   15   7
返回：3

限制：

  1. 节点总数 <= 10000

解题思路

获得二叉树最大深度，可以叫二叉树自根节点遍历至每一个子节点，记录最大深度并返回

也可以拆分任务：获得每一个子节点的最大深度并返回

对于每一个节点而言，获取其左右节点的深度，取大值 + 1 ( 当前节点 ) 并返回

需要额外考虑的就是叶子节点，当前遍历到叶子节点时，判断左右为null的分支深度为0即可

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

平衡二叉树

Esay 原题连接：平衡二叉树

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

示例：

    3
   / \
  9  20
    /  \
   15   7
输出: True
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
输出：False

提示：

  1. 0 <= 树的结点个数 <= 10000

解题思路

判断某树是否是平衡二叉树时，需要确定二叉树中任意节点的左右子树深度差不超过1

对于每一棵子树，都需要知道其左右子树深度，也需要向上返回深度+1以告知父节点当前最大深度

定义一个成员变量 flag 检测是否存在非平衡树的子树，当完成遍历后，flag 仍未改变则说明当前树为平衡二叉树

否则不是

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean flag = true;
    public boolean isBalanced(TreeNode root) {
        int ans = treeLen(root);
        return flag;
    }

    public int treeLen(TreeNode root) {
        if(!flag) return 0;
        if(root == null) return 0;
        int leftLen = treeLen(root.left);
        int rightLen = treeLen(root.right);
        if(leftLen - rightLen >=-1 && leftLen - rightLen <= 1) {
            return 1 + Math.max(leftLen, rightLen);
        }
        flag = false;
        return 0;
    }
}