Posted on 2014-01-18 16:55
Uriel 閱讀(133)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
LeetCode
判斷二叉樹是否平衡，即其中每一個(gè)節(jié)點(diǎn)的左右子樹深度差不大于1，一開始理解錯(cuò)題意。。。
于是DFS，分別找兩顆子樹中節(jié)點(diǎn)的最大深度，判相差是否不大于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 };