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 depth of the two subtrees of?every?node never differ by more than 1.

?

可以先求出每個subtree的深度，然后比較。但不高效，時間復雜度為O(nlgn).因為每一次計算左右subtree深度為2*O(lgn), 然后遞歸n次。

public bool IsBalanced(TreeNode root) {if(root == null) return true;int left = TreeHeight(root.left);int right = TreeHeight(root.right);if ((left>=right+2)||(left+2<=right)) return false;return IsBalanced(root.left)&& IsBalanced(root.right);}public int TreeHeight(TreeNode root){if(root == null) return 0;if(root.left == null && root.right == null) return 1;return Math.Max(TreeHeight(root.left), TreeHeight(root.right))+1;}

?

優化的方法為DFS，先check更小的subtree是否為Balanced Tree, 如果不是則直接返回false。參考http://www.cnblogs.com/grandyang/p/4045660.html

?

public bool IsBalanced(TreeNode root) {return !(TreeHeight(root)==-1);}public int TreeHeight(TreeNode root){if(root == null) return 0;int left = TreeHeight(root.left);if(left == -1) return -1;int right = TreeHeight(root.right);if(right == -1) return -1;if ((left>=right+2)||(left+2<=right)) return -1;return Math.Max(left, right)+1;}

?

轉載于:https://www.cnblogs.com/renyualbert/p/5863170.html

總結

以上是生活随笔為你收集整理的110. Balanced Binary Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。