首页 > 代码库 > [LeetCode] [Balanced Binary Tree 2012-10-08 ]
[LeetCode] [Balanced Binary Tree 2012-10-08 ]
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.
The key problem is that recursive func should return not only T/F to indicate if subtree is balanced, but also the depth for parent root to decide if left/right has the same depth.
we use the TreeNode->val to store the depth, so an initialize of val is needed at first.
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | class Solution { public : void ResetTree(TreeNode * root) { if (root == NULL) { return ; } root->val = 0; ResetTree(root->left); ResetTree(root->right); } bool treeSet = false ; bool isBalanced(TreeNode *root) { if (treeSet == false ) { ResetTree(root); treeSet = true ; } if (root == NULL) return true ; bool b1 = isBalanced(root->left); bool b2 = isBalanced(root->right); if (b1 == false || b2 == false ) { return false ; } int d1 = 0; int d2 = 0; if (root->left) { d1 = root->left->val; } if (root->right) { d2 = root->right->val; } if (d1 > d2) { root->val = d1+1; } else { root->val = d2+1; } if ((d1-d2)>1 || (d1-d2)<-1) { return false ; } return true ; } }; |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。