LCOF55_I && LCOF55_II

[underwindfall]

• https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

• https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

• 思路

  • dfs

• [x] 刷15mins

• [x] 刷5mins

public class LCOF55_I {
    // time O(n)
    // space O(n)
    class DFS {
        public int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            int level = Math.max(left, right);
            return level + 1;
        }
    }

// time O(n * logN)
    // space O(n)
    class DFS {
        public boolean isBalanced(TreeNode root) {
            if (root == null) {
                return true;
            }
            int leftLevel = dfs(root.left);
            int rightLevel = dfs(root.right);
            return Math.abs(rightLevel - leftLevel) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }

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