LeetCode-Balanced Binary Tree

平衡二叉树的判断，DFS，

一直没想到怎么同时返回结点的长度和状态，把高度放到参数里面比较简便！

 1 class Solution {
 2 public:
 3     bool isBalanced(TreeNode *root) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         int height = 0;
 7         return getHeight(root, height);
 8         
 9     }
10     bool getHeight(TreeNode *root, int &height) {
11         if (!root) {
12             return true;
13         }
14         int leftheight = 0;
15         int rightheight = 0;
16         if (getHeight(root->left, leftheight) && getHeight(root->right, rightheight)) {
17             height = max(leftheight, rightheight) + 1;
18             if (abs(leftheight - rightheight) <= 1) {
19                 return true;
20             }
21         }
22         return false;
23     }
24 };

不过其实不需要用两个变量来表示状态，可以直接用一个int返回值来表示，

如果是false的则直接返回-1，否则返回高度：

 1 class Solution {
 2 public:
 3     bool isBalanced(TreeNode *root) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         int ret = getHeight(root);
 7         if (ret == -1) {
 8             return false;
 9         }
10         return true;
11     }
12     int getHeight(TreeNode *root) {
13         if (root == NULL) {
14             return 0;
15         }
16         int left = getHeight(root->left);
17         int right = getHeight(root->right);
18         if (left == -1 || right == - 1) {
19             return -1;
20         }
21         if (abs(left - right) > 1) {
22             return -1;
23         }
24         return (max(left, right) + 1);
25     }
26 };