LeetCode 110. Balanced Binary Tree

原題連結在這裡：https://leetcode.com/problems/balanced-binary-tree/

題目：

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Given the following tree 

[3,9,20,null,null,15,7]

:

3
   / \
  9  20
    /  \
   15   7      

Return true.

Example 2:

[1,2,2,3,3,null,null,4,4]

1
      / \
     2   2
    / \
   3   3
  / \
 4   4
      

Return false.

題解：

Get 最大深度.如果左右最大深度相差大于一，則傳回-1. 若是已有左或者右的傳回值為-1, 即傳回-1.

最後看傳回到root時是否為一個負數，若是負數則不是balanced, 若是正數，則傳回了最大深度，是balanced.

Time Complexity: O(n).

1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public boolean isBalanced(TreeNode root) {
12         return maxDepth(root) >= 0; 
13     }
14     
15     private int maxDepth(TreeNode root){
16         if(root == null){
17             return 0;
18         }
19         int leftDepth = maxDepth(root.left);
20         int rightDepth = maxDepth(root.right);
21         if(leftDepth == -1 || rightDepth == -1 || Math.abs(leftDepth - rightDepth) > 1){
22             return -1;
23         }
24         return Math.max(leftDepth, rightDepth) + 1;
25     }
26 }