Title
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.
Tag: Tree, Deep-first Search
Solution
判断一棵树是否为AVL树,也就是对于每个节点来说,判断当前节点的左右子树高度差的绝对值是否小与1。
如果小于1,说明当前节点为跟节点的树为AVL树。所以,很容易想到用递归求解。
下面直接贴上AC代码。
AC Code
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
* Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution {public : bool (TreeNode* root) { if (root == nullptr ) return true ; if (root->left == nullptr && root->right == nullptr ) return true ; if (abs (depth(root->left) - depth(root->right)) > 1 ) return false ; return isBalanced(root->left) && isBalanced(root->right); } private : int depth (TreeNode *root) { if (root == nullptr ) return 0 ; return max(depth(root->left), depth(root->right)) + 1 ; } };
近期评论