原文链接 [每日 LeetCode] 110. Balanced Binary Tree
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.
Example 1:
Given the following tree [3,9,20,null,null,15,7]
:
3 / \ 9 20 / \ 15 7
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]
:
1 / \ 2 2 / \ 3 3 / \ 4 4
Return false.
思路:本题要求判断一棵树是否是平衡二叉树。使用到了辅助函数[每日 LeetCode] 104. Maximum Depth of Binary Tree,对原树进行递归依次判断左右子树的最大深度,小于 1 则返回 true。
C++ 代码
/** * 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 isBalanced(TreeNode* root) { if (!root) return true; int lheight = maxDepth(root->left); int rheight = maxDepth(root->right); if (abs(lheight - rheight) <= 1) return isBalanced(root->left) && isBalanced(root->right); else return false; } int maxDepth(TreeNode* root) { if(!root) return 0; else { int left = maxDepth(root->left); int right = maxDepth(root->right); return left>right?left+1:right+1; } } };
运行时间:8ms
运行内存:16.5M
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于