55-二叉树的深度、平衡二叉树

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

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

还可以使用 按层序遍历，每遍历到一层，层数加1

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
        int res = 0;
        while(!queue.isEmpty()) {
            tmp = new LinkedList<>();
            for(TreeNode node : queue) {
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            queue = tmp;
            res++;
        }
        return res;
    }
}

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

自上至下求深度时，可以用Map缓存

public class Solution {
    Map<TreeNode, Integer> map = new HashMap<>();
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;
        int leftDeep = 0;
        int rightDeep = 0;
        if (map.containsKey(root.left)) {
            leftDeep = map.get(root.left);
        } else {
            leftDeep = getDeep(root.left);
        }
        if (map.containsKey(root.right)) {
            rightDeep = map.get(root.right);
        } else {
            rightDeep = getDeep(root.right);
        }
        return Math.abs(leftDeep - rightDeep) <= 1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    
    private int getDeep(TreeNode node) {
        if (node == null) return 0;
        int deep = 1 + Math.max(getDeep(node.left), getDeep(node.right));
        map.put(node, deep);
        return deep;
    }
}