Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Balanced Binary Tree-2014.01.18

Posted on 2014-01-18 16:55 Uriel 阅读(101) 评论(0)  编辑 收藏 引用 所属分类: LeetCode
判断二叉树是否平衡,即其中每一个节点的左右子树深度差不大于1,一开始理解错题意。。。
于是DFS,分别找两颗子树中节点的最大深度,判相差是否不大于1即可

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool res;
13     int DFS(TreeNode *root) {
14         if(!res || root == NULL) return 0;
15         int ld = DFS(root->left);
16         int rd = DFS(root->right);
17         if(abs(ld - rd) > 1) res = false;
18         return max(ld, rd) + 1;
19     }
20     
21     bool isBalanced(TreeNode *root) {
22         if(root == NULL) return true;
23         res = true;
24         DFS(root);
25         return res;
26     }
27 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理