欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 110. Balanced Binary Tree

程序员文章站 2024-03-19 19:13:50
...

题目描述

LeetCode 110. Balanced Binary Tree

知识点

二叉树递归自底向上 + 提前隔断

结果

LeetCode 110. Balanced Binary Tree
这个程度的时空复杂度可以啦

实现

码前思考

  1. 由于涉及到了高度,所以一定要有高度这个变量,由于TreeNode结构体定死了,所以我们采用局部变量来存储左右子树的高度,然后就是简单的判断即可。

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 //递归判断当前的树是否是否是平衡二叉树
 //对于这种true or false的题目,常见的递归式就是左右子树的&&运算
 //需要记录子树的高度
class Solution {
private:
    bool flag;
public:
    bool isBalanced(TreeNode* root) {
        //注意空树是否需要判断

        flag = true;    //初始化为true

        //记录左子树和右子树的高度
        int height;

        judge(root,height);

        return flag;
    }

    //判断当前以root为根的树是否是平衡二叉树,height表示当前子树的高度
    int judge(TreeNode* root,int& height){
        if(root == NULL){
            height = 0;
        }else if(flag == true){ //设置一个true判断,一定程度上减少不必要的递归
            //记录左子树和右子树的高度
            int lHeight;
            int rHeight;
            
            judge(root->left,lHeight);
            judge(root->right,rHeight);

            height = max(lHeight,rHeight) + 1;

            if(abs(lHeight - rHeight) > 1){
                flag = false;
            }
        }

        return height;
    }
};

码后反思

  1. 看了题解,发现自己使用的是自底向上的方法来判断,而且还是使用了一个bool变量flag来进行提前的隔断。
相关标签: #