【二叉树专题】剑指 Offer 55 – II. 平衡二叉树-跟着帅地玩副业，开拓第二曲线PlayOffer

小火普通 2023年10月3日下午11:57

时间复杂度：o(n^2)
空间复杂度：o(n)

 /*
 只需要判断根节点的左右子树的高度差就行
 */
class Solution {
private:
    int depth(TreeNode* node) {
        if(node == nullptr)
            return 0;
        return(max(depth(node->left), depth(node->right))+1);
    }
public:
    bool isBalanced(TreeNode* root) {
        if(root == nullptr)
            return true;
        if(abs(depth(root->left)-depth(root->right))>1)
            return false;
        return(isBalanced(root->left)&&isBalanced(root->right));
        // return true; 

    }
};

0 赞同 0 条回复

谁仁普通 2023年9月11日下午2:30

int getHeight(TreeNode* node) {
if (node NULL) {
return 0;
}
int leftHeight = getHeight(node->left);
int rightHeight = getHeight(node->right);
if (leftHeight – rightHeight > 1 || leftHeight – rightHeight < -1) //判断左右树是否平衡，如果不平衡就返回0，直接false
{
return 0;
}
return 1 + max(leftHeight, rightHeight); //返回深度
}

bool isBalanced(TreeNode* root) {
return getHeight(root) != 0; //返回判断
}
//时间复杂度：O(n^2)，空间复杂度：O(n)

0 赞同 0 条回复

黎明之前普通 2023年9月3日下午12:31

//时间复杂度和空间复杂度为O(n)

class Solution{
public: bool isBalanced(TreeNode *root)
{if(root NULL) return true;
if(MaxDepth(root) -1) return false;
return ture;
}
int MaxDepth(TreeNode *root){
if(root NULL) return NULL;
int left = MaxDepth(root->left);
if(left -1) return -1;
int right = MaxDepth(root->right);
if(right -1) return -1;
if(abs(left-right)-1) return -1;
return max(left,right)+1;
}
};

0 赞同 0 条回复

Marc 普通 2023年8月31日上午12:41

class Solution:
    res = True  
    def isBalanced(self, root: TreeNode) -> bool:
        def height(root):
            if not root:
                return 0 
            left_height = height(root.left)
            right_height = height(root.right)
            if (abs(left_height - right_height) > 1):
                self.res = False
            return max(left_height, right_height) + 1 

        height(root)
        return self.res

时间On 空间On

0 赞同 0 条回复

Di questa storia sempre a lie to 普通 2023年8月27日下午10:20

/**
* 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 height(TreeNode root){
if (root nullptr) return 0;
int leftheight = height(root->left);
int rightheight = height(root->right);
if(leftheight -1 || rightheight -1 || abs(leftheight – rightheight)>1){
return -1;
}
else{
return max(leftheight, rightheight) + 1;
}
}

bool isBalanced(TreeNode* root) {
  return height(root) >=0;
}

};
时间复杂度：O(N)
空间复杂度：O(N)

0 赞同 0 条回复

Miracle· 普通 2023年8月27日上午11:10

/**
* 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 nullptr) return true;
// else {
// return abs(height(root->left) – height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
// }
// }

// int height(TreeNode* root) {
//     if (root == nullptr) {
//         return 0;
//     }else {
//         return max(height(root->left), height(root->right)) + 1;
//     }
// }

// 自底向上,后序的思想
bool isBalanced(TreeNode* root) {
    return height(root) >= 0;
}

int height(TreeNode* root) {
    if (root == nullptr) return 0;
    int leftheight = height(root->left);
    int rightheight = height(root->right);
    if (leftheight == -1 || rightheight == -1 || abs(leftheight - rightheight) > 1) {
        return -1;
    }else {
        return max(leftheight, rightheight) + 1;
    }
}

};

0 赞同 0 条回复

sc_Yang 普通 2023年8月24日上午9:11

计算深度差，并且保证该节点的子树也是平衡二叉树

/**
 * 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 maxDepth(TreeNode* root) {
        int depth = 0;
        if(root == NULL){
            return 0;
        }
        int depthL = maxDepth(root->left) + 1;
        int depthR = maxDepth(root->right) + 1;
        depthL>depthR ? depth = depthL : depth = depthR;
        return depth;
    }
    bool isBalanced(TreeNode* root) {
        if(root==NULL){
            return true;
        }
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        return abs(leftDepth - rightDepth) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

0 赞同 0 条回复

sincere 普通 2023年8月22日下午10:38

思路：1、递归计算左右子树深度，相差应该小于1，并且左右子树也要是平衡的，即三个条件相与；2、剪枝，后序遍历方式先计算子树深度在计算当前根节点深度，对于遇到不平衡的子树直接向上返回
复杂度：空间复杂度O(n)，时间复杂度O(n)

// 递归
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        Integer left = maxDepth(root.left);
        Integer right = maxDepth(root.right);
        return isBalanced(root.left) && isBalanced(root.right) && Math.abs(left - right) <= 1;
    }

    Integer maxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        Integer left = maxDepth(node.left);
        Integer right = maxDepth(node.right);
        return Math.max(left, right) + 1;
    }
}
// 剪枝
class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    // 后序遍历 左、右、根,用-1表示不平衡情况
    Integer recur(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 左右子树 有-1情况就直接往上返回
        int left = recur(node.left);
        if (left == -1) {
            return -1;
        }
        int right = recur(node.right);
        if (right == -1) {
            return -1;
        }
        // 当前根节点时才计算当前节点的深度
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

0 赞同 0 条回复

💮黧大王.exe 普通 2023年8月21日下午10:49

时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public:
int height(TreeNode* root){
if(rootNULL) return 0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (leftHeight-1||rightHeight-1||abs(leftHeight-rightHeight)>1) {
return -1;
} else {
return max(leftHeight, rightHeight) + 1;
}
}
bool isBalanced(TreeNode* root) {
return height(root)>=0;
}
};

0 赞同 0 条回复

Sheng 永久会员 2023年8月21日下午3:22

没有思路，根据答案写的
关于剪枝的思路还有更多练习
”’java
class Solution {

//判断是否是平衡二叉树
public boolean isBalanced(TreeNode root) {
    if(root == null) return true;

    return maxDepth(root) != -1;
}
    //二叉树的最大深度
public int maxDepth(TreeNode root) {
    if(root == null) return 0;

    int depLeft = maxDepth(root.left);
    if(depLeft == -1) return -1;
    int depRight = maxDepth(root.right);
    if(depRight == -1) return -1;
    //将节点深度计算与是否平衡一起计算，每个节点只计算一次
    if(Math.abs(depRight-depLeft)>1) return -1;

    return Math.max(depLeft,depRight) + 1;
}

}

0 赞同 0 条回复

木木普通 2023年8月21日下午1:53

先用遞歸方式計算出每個節點的深度, 接著我們只要找出左右深度差小於1的node就返回true, 若沒有則返回false;
也同樣做遞歸求解.
時間複雜度: O(n) 空間複雜度: O(n) 取決於遞歸調用的層數, n為節點總個數


class Solution {
public:
    bool isBalanced(TreeNode* root) {
      if (root == NULL) {
        return true;
      }
      int left = findDepth(root->left);
      int right = findDepth(root->right);
      
      return std::abs(left-right) <= 1 && isBalanced(root->left) && isBalanced(root->right); 

    }

    int findDepth(TreeNode* root) {
      if (root == nullptr) {
        return 0;
      }
      int left = findDepth(root->left);
      int right = findDepth(root->right);
      return std::max(left, right) + 1;
    }
};

0 赞同 0 条回复

小肸永久会员 2023年8月20日下午9:15

class Solution {
    boolean flag = true;
    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return flag;
    }
    private int dfs(TreeNode node) {
        //flag==false说明此树已经不满足平衡二叉树，没有必要继续递归
        if (node == null || !flag) {
            return 0;
        }
        int leftHeight = dfs(node.left);
        int rightHeight = dfs(node.right);
        if (Math.abs(leftHeight - rightHeight) > 1) {
            flag = false;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

0 赞同 0 条回复

辰北、普通 2023年8月20日下午8:18

//时间on，空间on，
int height(struct TreeNode* root){
if(root NULL){
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if(leftHeight -1 || rightHeight -1 || fabs(leftHeight-rightHeight) > 1 ){
return -1;

}else{
    return fmax(leftHeight,rightHeight) + 1;
}

}
bool isBalanced (struct TreeNode* root){
return height(root) >= 0;
}

0 赞同 0 条回复

天亮说晚安普通 2023年8月20日下午2:58

时间复杂度O(n^2)，空间复杂度O(n)

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int lhight = maxDepth(root.left) + 1;
        int rhight = maxDepth(root.right) + 1;
        return lhight>rhight ? lhight : rhight;
    }
}

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月19日下午1:47


Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
    def depth(self, root:TreeNode):
        if not root:return 0
        #先左子树递归，并且给定左子树递归结束条件
        depleft = self.depth(root.left)
        if depleft  -1: return -1
        #然后右子树递归，给定右子树递归结束条件
        depright = self.depth(root.right)
        if depright -1: return -1

    return max(depleft,depright)+1 if abs(depleft-depright)<=1 else -1

    '''if not root: return 0
    return max(self.depth(root.left), self.depth(roo.right))+1'''

def isBalanced(self, root: TreeNode) -> bool:

    return self.depth(root) != -1

    '''if not root: return 0

    return if abs(self.depth(root.left)-self.depth(root.right))<=1 and self.isBalanced(self.left) and self.isBalanced(self.right)'''

0 赞同 0 条回复

Jou Siankwa 普通 2023年8月18日下午10:52

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        if(depth(root) != -1){
            return true;
        }else {
            return false;
        }
    }

    private int depth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        if(Math.abs(left - right) > 1 || left == -1 || right == -1){
            return -1;
        }else {
            return Math.max(left,right) + 1;
        }
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(3);
        TreeNode node5 = new TreeNode(3);
        TreeNode node6 = new TreeNode(4);
        TreeNode node7 = new TreeNode(4);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node4.left = node6;
        node4.right = node7;

        Solution sol = new Solution();
        boolean b = sol.isBalanced(node1);
        System.out.println(b);
    }
}

左子树与右子树高度差绝对值大于1，返回-1，左子树或右子树为-1，该节点返回-1

0 赞同 0 条回复

逸兴遄飞普通 2023年8月18日上午9:40

自顶而下的递归
+ 时间复杂度O(N)：所有节点只会遍历一遍，不会出现重复计算
+ 空间复杂度O(N)：所用空间只取决于递归调用的层数，最大为节点数N

class Solution {
    // 借助flag做剪枝，优化算法
    boolean flag = true;
    // 返回判断的主函数
    public boolean isBalanced(TreeNode root) {
        height(root);
        return flag;
    }
    // 自顶而下计算节点左右子树的高度，判断高度差是否超过1，不超过则递归地遍历左右子节点，重新进行计算判断
    public int height(TreeNode node) {
        if(node == null || !flag) return 0;
        int leftnode = height(node.left);
        int rightnode = height(node.right);
        if(Math.abs(leftnode - rightnode) > 1) flag = false;
        return Math.max(leftnode, rightnode) + 1; 
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月17日下午11:17

1、回溯

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(deep(root) == -1){
            return false;
        }
        return true;
    }

    public int deep(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = deep(root.left);
        if(left == -1){
            return -1;
        }
        int right = deep(root.right);
        if(right == -1){
            return -1;
        }
        if(Math.abs(left - right) > 1){
            return -1;
        }
        return left > right? left+1 : right+1;
    }
}

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月17日下午10:37

一个平衡二叉树，它的左子树和右子树都要是平衡二叉树，并且左右子树的深度相差不能超过1。
class Solution {
public boolean isBalanced(TreeNode root) {
if(root null){
return true;
}else{
return isBalanced(root.left) && isBalanced(root.right) && Math.abs(depth(root.left) – depth(root.right)) <= 1;
}
}
public int depth(TreeNode root){
if(root null){
return 0;
}
return Math.max(depth(root.left), depth(root.right)) + 1;
}
}

0 赞同 0 条回复

帝心引力永久会员 2023年8月17日下午10:12

class Solution {
public:
    int depth(TreeNode* root){
        if(root == NULL) return 0;
        int ldepth = depth(root->left);
        int rdepth = depth(root->right);

        // 如果子树有不平衡的了或者当前不平衡
        if(ldepth == -1 || rdepth == -1 || abs(ldepth - rdepth) > 1){
            return -1;
        }
        // 否则返回树的高度
        return max(ldepth, rdepth) + 1;
    }
    bool isBalanced(TreeNode* root) {
        // 如果是平衡二叉树，会返回树的高度
        // 不平衡的会返回-1
        return depth(root) >= 0;
    }
};
时间o(n), 空间o(h)

0 赞同 0 条回复

晓宇普通 2023年8月17日下午9:44

class Solution(object):
    def __init__(self):
        self.found = True
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.get_depth(root)
        return self.found


    def get_depth(self,root):
        if not root:
            return 0
        left_depth = self.get_depth(root.left)
        right_depth = self.get_depth(root.right)
        if abs(left_depth - right_depth) >= 2:
            self.found = False
        return max(left_depth,right_depth)+1

just traverse with a flag 啊

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月17日下午9:13

时间复杂度O(n), 空间复杂度O(n)

lass Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return height(root) != -1;
    }
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(rightHeight - leftHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年8月17日下午8:27

 // 自顶向下，一层层高度对比
 // 时间复杂度O(n^2),空间O(n)
class Solution {
public:
    int maxdeth(TreeNode* root)
    {
        if(!root) return 0;
        int left = maxdeth(root->left);
        int right = maxdeth(root->right);
        return max(left,right)+1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int left = maxdeth(root->left);
        int right = maxdeth(root->right);
        if(abs(left-right)>1) return false;

        return isBalanced(root->left)&&isBalanced(root->right);
    }
};
//自底向上
// 时间O(n),空间O(n)
class Solution {
public:
    int maxdeth(TreeNode* root)
    {
        if(!root) return 0;
        int left = maxdeth(root->left);
        if(left==-1) return -1;
        int right = maxdeth(root->right);
        if(right==-1) return -1;
        if(abs(left-right)>1) return -1;
        return max(left,right)+1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        if(maxdeth(root)==-1) return false;
        return true;
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年8月17日下午5:03

// 递归求深度的时候，如果当前节点不平衡（ldeep-rdeep>1)，连续向上返回-1
// 时间复杂度O(n), 空间复杂度O(n)

class Solution {
public:
    bool isBalanced(TreeNode* root) {
         return deep(root) != -1;
    }

    int deep(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int ldeep = deep(root->left);
        int rdeep = deep(root->right);
        if (ldeep == -1 || rdeep == -1) {
            return -1;
        }
        if (ldeep > rdeep) {
            if (ldeep - rdeep > 1) {
                return -1;
            }
            return ldeep + 1;
        } else {
            if (rdeep - ldeep > 1) {
                return -1;
            }
            return rdeep + 1;
        }
    }
};

0 赞同 0 条回复

Joel 普通 2023年8月17日下午4:11

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def balanced(root):
            if root == None:
                return 0
            if root.left == None and root.right == None:
                return 1
            return 1+max(balanced(root.left), balanced(root.right))
        if root == None:
            return True
        elif root.left == None:
            return balanced(root.right)<=1
        elif root.right == None:
            return balanced(root.left)<=1
        return self.isBalanced(root.left) and self.isBalanced(root.right) and abs(balanced(root.left)-balanced(root.right))<=1

0 赞同 0 条回复

c 普通 2023年8月17日下午1:42

递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root==null){
            return true;
        }
        int res = Math.abs(getDeep(root.left)-getDeep(root.right));
        return (res==1 || res==0) &&  isBalanced(root.left) && isBalanced(root.right);

    }
    public static int getDeep(TreeNode root){
        if(root==null){
            return 0;
        }
        return 1+Math.max(getDeep(root.left),getDeep(root.right));
    }
}

0 赞同 0 条回复

【二叉树专题】剑指 Offer 55 – II. 平衡二叉树

共以下 26 个回答

# 回答此问题取消回复

【二叉树专题】剑指 Offer 55 – II. 平衡二叉树

共以下 26 个回答

# 回答此问题 取消回复

# 回答此问题取消回复