通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            jpress从3.x升级到4.x,显示有些问题,慢慢修复中

leetcode 剑指 Offer 55 - II. 平衡二叉树

418人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/871

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false 。

限制:

  • 0 <= 树的结点个数 <= 10000

难度:简单;标签:树,深度优先搜索;编程语言: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 {
    bool res;
public:
    bool isBalanced(TreeNode* root) {
        int h = 0;
        res = true;
        heightBalance(root, &h);

        return res;
    }

    void heightBalance(TreeNode* node, int* h){
        if(!res)return;

        if(node){
            if(!node->left && !node->right){
                *h = 1;
            }else{
                *h = 0;
                heightBalance(node->left, h);
                int l = *h;

                *h = 0;
                heightBalance(node->right, h);
                int r = *h;

                if(abs(r - l) > 1)res = false;
                *h = max(l, r) + 1;
            }
        }
    }
};

方法:找出左右深度,判断是否平衡,然后加上自己的深度1,供上一层次使用,如果出现不平衡,就可以return了

实现:深度递归,用一个指针h记录深度,分别计算左、右深度和当前深度(max(l, r)+1),判断平衡


其它解法

/**
 * 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:
   int recur(TreeNode* root)
   {
    //    叶子结点,0层
       if(root==NULL)
         return 0;
        int leftlevel=recur(root->left);
        if(leftlevel==-1)
        {
            return -1;
        }
        int rightlevel=recur(root->right);
        if(rightlevel==-1)
           return-1;
        if(rightlevel-leftlevel>1||rightlevel-leftlevel<-1)
           return -1;
        else
        {
            return max(rightlevel,leftlevel)+1;
        }
   }
    bool isBalanced(TreeNode* root) {
        if(recur(root)==-1)
         return false;
        else 
         return true;

    }
};

基本一致,不再多说,区别是我的解法把深度保存在参数*h中,这里保存在返回值中


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告