网站建设中 模板,wordpress禁用谷歌字体,公司建设网站的意义,网站新闻后台怎么做110. 平衡二叉树#xff08;简单#xff09; 思路 对二叉树做先序遍历#xff0c;从底至顶返回子树最大高度#xff0c;若判定某子树不是平衡树则“剪枝”直接向上返回。 递归返回值#xff1a; 当节点 root 左、右子树的高度差 1#xff1a;返回 -1#xff0c;代…110. 平衡二叉树简单 思路 对二叉树做先序遍历从底至顶返回子树最大高度若判定某子树不是平衡树则“剪枝”直接向上返回。 递归返回值 当节点 root 左、右子树的高度差 1返回 -1代表此子树不是平衡树否则返回以节点 root 为根节点的子树的最大高度即节点 root 的左、右子树中最大高度加1 (max(leftright) 1)。 递归终止条件 当抵达叶子节点时返回高度 0当左(右)子树高度 left/right -1 时代表此子树的左子树不是平衡树因此直接返回 -1 isBalanced(root) 返回值: 若 helper(root) ! 1 则说明此树平衡返回 true ; 否则返回 false。
代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isBalanced(TreeNode* root) {// -1 表示不平衡return helper(root) ! -1;}// 计算高度int helper(TreeNode* root){if(root nullptr) return 0;int left helper(root-left), right helper(root-right);// -1 表示不平衡if(left -1 || right -1 || abs(left-right)1){return -1;}// 返回子树的高度return max(left, right) 1;}
};
