leetcode 110. Balanced Binary Tree

2017-02-24 · 1 min read

题目链接

题意：判断一颗二叉树是否平衡....

思路：直接搞就好了。。。神TM又忘记dfs的时候忘记返回子调用的值。。。。我这是药丸啊。。。

 1 /**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10class Solution {  //错误原因：左右子树都平衡的树未必平衡！！！！
11public:
12		bool leaf(TreeNode* root)
13		{
14			if (root->left==NULL&&root->right==NULL) return true;
15			return false;
16		}
17		int dep(TreeNode* root)
18		{
19			if (root==NULL) return 0;
20			return max(dep(root->left),dep(root->right))+1;
21		}
22		bool dfs(TreeNode* root)
23		{
24				bool res = true;
25				if (abs(dep(root->left)-dep(root->right))>1) return false;
26				if (root->left!=NULL) res = dfs(root->left);
27				if (!res) return false;
28				if  (root->right!=NULL) res = dfs(root->right);
29				if (!res) return false;
30				return true;		
31		}
32    bool isBalanced(TreeNode* root) {
33		if (root==NULL) return true;
34		bool res = dfs(root);
35		return res;
36    }
37};