剑指offer39平衡二叉树判断

平衡二叉树

https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&&tqId=11192&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

剑指offer39平衡二叉树判断

剑指offer39

图片说明

1、常规思路
封装一个求节点深度的方法,然后遍历树,调用该方法并判断是否符合平衡二叉树
时间复杂度O(n^2) 空间复杂度O(n^2),主要是递归的原因
个人解题参考

class Solution {
public:
    int TreeDepth(TreeNode* pRoot) //节点深度
    {
        if(!pRoot) return 0;
        return max(TreeDepth(pRoot->left),TreeDepth(pRoot->right))+1;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        stack<TreeNode*>st; //通过栈迭代中序遍历
        while(pRoot||st.size()!=0)
        {
            while(pRoot)
            {
                st.push(pRoot);
                pRoot=pRoot->left;
            }
            pRoot=st.top();
            st.pop();
            while(abs(TreeDepth(pRoot->left)-TreeDepth(pRoot->right))>1)
            {
                return false;
            }
            pRoot=pRoot->right;
        }
        return true;
    }
};

2、对上述时间空间优化
两层循环遍历实际不必要,内层求节点深度的遍历的同时就可以直接判断每个节点为根节点的子树是否平衡,平衡则继续递归判断计算其他节点深度并判断,不平衡则停止后续递归。我们需要的仅是一个是否平衡二叉树的标记
时间复杂度:O(n) 空间复杂度:O(1)
个人解题参考

class Solution {
public:
    bool flag=true; //是否为平衡二叉树
    int TreeDepth(TreeNode* pRoot) //节点深度
    {
        if(!flag) return -1;  //若已经判断不是平衡二叉树,接下来的递归无需继续进行
        if(!pRoot) return 0;
        int leftChild_depth=TreeDepth(pRoot->left)+1;
        int rightChild_depth=TreeDepth(pRoot->right)+1;
        if(abs(leftChild_depth-rightChild_depth)>1)  //不是平衡二叉树
            flag=false;
        return max(leftChild_depth,rightChild_depth);
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
       TreeDepth(pRoot);
       return flag;
    }
};
全部评论
方法2纠正:递归存在,(最坏)空间复杂度O(n)
点赞 回复 分享
发布于 2021-05-31 19:22

相关推荐

07-04 16:00
门头沟学院 Java
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务