kfaebot 普通 2024年3月13日下午9:54

/**
 * 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:
    //步骤1：定义返回值和参数
    int getheight(TreeNode* node){
        //步骤2：定义终止条件
        if(node==nullptr){
            return 0;
        }

        //步骤3：定义遍历过程
        int leftheight=getheight(node->left);
        if(leftheight==-1){
            return -1;
        }

        int rightheight=getheight(node->right);
        if(rightheight==-1){
            return -1;
        }

        int result;
        if(abs(leftheight-rightheight)<=1){
            result=max(leftheight,rightheight)+1;
        }
        else{
            result=-1;
        }
        return result;
    }

    bool isBalanced(TreeNode* root) {
        if(getheight(root)==-1){
            return false;
        }
        else{
            return true;
        }
    }
};

0 赞同 0 条回复

RunAsOne 普通 2024年3月12日下午1:17

第n次打卡

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


    def isBalanced(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        if not root:
            return True
        if self.calculateDepth(root) == -1:
            return False
        return True
    def calculateDepth(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if not root:
            return 0
        left = self.calculateDepth(root.left)
        if left == -1:
            return -1
        right = self.calculateDepth(root.right)
        if right == -1:
            return -1
        if abs(left-right)>1:
            return -1
        return max(left, right) + 1

0 赞同 0 条回复

HU 普通 2024年3月12日上午9:53

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    if(root == null) return true;
    // 如果根节点不为平衡二叉树，则返回-1
    if(treeDepth(root) == -1) return false;
    return true;
};

const treeDepth = (root) => {
    if(root == null) return 0;
    let left = treeDepth(root.left);
    // 如果该节点的左子树不为平衡二叉树，则直接返回-1
    if(left == -1) return -1;
    let right = treeDepth(root.right);
    // 如果该节点的右子树不为平衡二叉树，则直接返回-1
    if(right == -1) return -1;
    // 如果该节点不为平衡二叉树，则返回-1
    if(Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
}

0 赞同 0 条回复

Let it be 永久会员 2024年3月11日下午5:29

class Solution {
public boolean isBalanced(TreeNode root) {
return recur(root) != -1;
}

public int recur(TreeNode root){
    if(root == null) return 0;
    int left = recur(root.left);
    if(left == -1) return -1;
    int right = recur(root.right);
    if(right == -1) return -1;
    return Math.abs(left-right) < 2 ? Math.max(left,right) +1 : -1;
}

}时间复杂度空间复杂度O（n）

0 赞同 0 条回复

小耿普通 2024年3月11日下午4:47

“`C++

class Solution {
public:
int CalDepth(TreeNode* root) {
if(root nullptr) return 0;
int left = CalDepth(root->left);
int right= CalDepth(root->right);
return max(left, right) + 1;
}
bool isBalanced(TreeNode* root) {
if (root nullptr) return true;
int left = CalDepth(root->left);
int right= CalDepth(root->right);
if ((left – right1 || left-right-1 || left right) && isBalanced(root->left) && isBalanced(root->right)) return true;
else return false;
}
};

“`C++
递归的三要素：
1）函数是干什么的
2）终结条件
3）找出函数的递归关系

0 赞同 0 条回复

MARS 普通 2024年3月10日下午11:39

day6第二题

function isBalanced(root: TreeNode | null): boolean {
    return getHeight(root) ==-1? false :true

    function getHeight(root: TreeNode | null): number {
        let res = 0  //平衡二叉树的深度
        if (root === null) return 0;  //如果无节点 返回0
        let left = getHeight(root.left)   //左节点的深度 
        if (left == -1) return -1  //拿到-1，一直返回上去
        let right = getHeight(root.right)
        if (right == -1) return -1
        if (Math.abs(left - right) > 1) return -1  //判断左右节点的相差是不是大于1
        else{
            res =  Math.max(left,right)+1
        }
        return res
    }
};

0 赞同 0 条回复

普通 2024年3月10日下午3:04

// 时间o(n) 空间o(n)
class Solution {
public:
bool isBalanced(TreeNode* root)
{
return Maxlength(root)>=0;
}

int Maxlength(TreeNode* root)
{
    // 递归的退出条件
    if(root == nullptr)   return 0;
    int l = Maxlength(root->left);
    int r = Maxlength(root->right);
    // 判断每个节点是否平衡，如果不平衡直接退出
    if(l==-1||r==-1||abs(l-r)>1)  return -1;
    return max(l,r)+1;
}

};

0 赞同 0 条回复

helloMoon 普通 2024年3月9日下午9:39

平衡二叉树java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        if(maxDepth(root) == -1)return false;
        return true;
    }

    public int maxDepth(TreeNode root){
        if(root == null) return 0;
        int left = maxDepth(root.left);
        if(left == -1) return -1;
        int right = maxDepth(root.right);
        if(right == -1) return -1;

        if(Math.abs(left - right) > 1) return -1;

        return Math.max(left, right) + 1;
    }
}

0 赞同 0 条回复

零普通 2024年3月9日下午9:36

代码:


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

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

0 赞同 0 条回复

=.= 普通 2024年3月9日下午6:46

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root null) return true;

    if(height(root) == -1) return false;
    return true;
}

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

}

时空复杂度O(n)

0 赞同 0 条回复

方铎码农普通 2024年3月9日上午11:41

 //采用后序遍历法，树的深度 = max(树.左 的深度，树.右的深度)+1，任何子树深度超过2则剪枝返回
class Solution {
    public boolean isBalanced(TreeNode root) {
       return recur(root)!=-1; 
    }

    private int recur(TreeNode root){
        if(root == null) return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2?Math.max(left,right)+1:-1;
    }
}

时间复杂度$O(n)$，空间复杂度$O(n)$，其巧妙之处在利用递归和树的后序遍历自底向上，每棵子树都是平衡二叉树则全树必定是平衡二叉树，符合平衡二叉树的定义。

0 赞同 0 条回复

mpweixin用户普通 2024年3月9日上午11:31

“`c++
//时间复杂度O()
class Solution {
public:
int getDepth(TreeNode* root){
if(!root)
return 0;
int left=getDepth(root->left);
if(left==-1)return -1;
int right=getDepth(root->right);
if(right==-1)return -1;
if((left-right)>1 || (left-right)<-1) return -1; return ((left>right)?left:right)+1;
}
bool isBalanced(TreeNode* root) {
if(!root)
return true;
if(getDepth(root)==-1)return false;
return true;

};

0 赞同 0 条回复

mpweixin用户普通 2024年3月8日下午10:17

java
class Solution{
public boolean isBalanced(TreeNode root){

        if(root == null){
            return true;
        }else{
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }


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

}
时间复杂度：O(n2)
空间复杂度：O(n)

0 赞同 0 条回复

东普通 2024年3月8日下午7:39

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return maxDepth(root) == -1 ? false:true  ;
    }
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        if (left == -1){
            return -1;
        }
        int right = maxDepth(root.right);
        if (right == -1){
            return -1;
        }
//比较深度差
        if(Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left,right) + 1;
    }
}

0 赞同 0 条回复

　南木普通 2024年3月8日下午5:24

// 时间 On,空间O

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        if(maxDepth(root) == -1) return false;
        return true;

    }

    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int left = maxDepth(root.left);
        if(left == -1) return -1;
        int right = maxDepth(root.right);
        if(right == -1) return -1;
        // 返回-1表示不符合条件了
        if(Math.abs(left - right) > 1) return -1;

        return Math.max(left, right) + 1;
    }
}

0 赞同 0 条回复

一个达不刘普通 2024年3月8日下午3:11

class Solution {
public:
//先序遍历，判断深度，比较左右子树深度差，若所有子树的深度差都<=1,则此树平衡

bool isBalanced(TreeNode* root) {
    if(root == nullptr) return true;
    return abs(depth(root->left) - depth(root->right) <=1 && isBalanced(root->left) &&isBalanced(root->right));//abs__求数据的绝对值。

}

private:
//计算二叉树高度
int depth(TreeNode * root){
if(root nullptr) return 0;
return max(depth(root->left),depth(root->right)) +1;
}

};
时间复杂度O（N^2）

0 赞同 0 条回复

南梁陈庆之普通 2024年3月8日下午2:59

从上向下递归，会重复计划，时间复杂度O（N^2）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            boolean flg = Math.abs(calculateDepth(node.left) - calculateDepth(node.right)) <= 1;
            if (!flg) {
                return false;
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

        return true;


    }



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

0 赞同 0 条回复

神经蛙普通 2024年3月8日上午12:13

class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root nullptr) return true;
if(calculateDepth (root) -1) return false;
return true;
}

int calculateDepth(TreeNode* root) {
    if(nullptr == root) return 0;
    int left = calculateDepth(root->left);
    if(left == -1) return -1;
    int right = calculateDepth(root->right);
    if(right == -1) return -1;
    if(abs(left - right ) > 1) return -1;

    return max(left,right) + 1;
}

};
时间复杂度O(n) 空间复杂度O（n）

0 赞同 0 条回复

heathhou 普通 2024年3月7日下午9:44

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == nullptr)
            return true;
        int res = maxDepth(root);
        return res == -1 ? false : true;
    }
    // 递归函数：求树的高度
    int maxDepth(TreeNode* root){
        // 递归结束条件
        if(root == nullptr) return 0;

        // 递归函数的等价关系式
        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 条回复

叫不醒装睡的人普通 2024年3月7日下午8:04

class Solution {
    // 判断是否为平衡二叉树，左右子树高度差不大于 1 
    // 简化计算，当左右子树高度差超过 1 时，直接返回 -1
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return height(root) != -1;
    }

    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftH = height(root.left);
        if (leftH == -1) {
            return -1;
        }
        int rightH = height(root.right);
        if (rightH == -1) {
            return -1;
        }
        if (Math.abs(leftH - rightH) > 1) {
            return -1;
        }
        return Math.max(leftH, rightH) + 1;
    }
    // 时间复杂度 O(n)
    // 空间复杂度 O(n)
}

0 赞同 0 条回复

Jimmy 普通 2024年3月7日下午8:04

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

/**
 * 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) {
        if(!root)return true;
        if(maxDepth(root) == -1){
            return false;
        }else{
            return true;
        }
    }

    int maxDepth(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        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 条回复

云无深雁影普通 2024年3月7日下午4:54

class Solution {
private int calDepth(TreeNode root){//递归计算深度的同时判断左右节点深度差，如果大于1则返回-1而不是深度值。
if(rootnull)
return 0;
int leftDepth = calDepth(root.left);
int rightDepth = calDepth(root.right);
int subtract = leftDepth – rightDepth;
if(leftDepth -1 || rightDepth-1 || subtract < -1 || subtract > 1)
return -1;
else
return Math.max(leftDepth,rightDepth)+1;
}

public boolean isBalanced(TreeNode root) {
    if(calDepth(root)==-1)
        return false;
    return true;

}

}
时间复杂度空间复杂度均为On

0 赞同 0 条回复

进取普通 2024年3月7日上午11:27

class Solution {
public:
bool isBalanced(TreeNode* root) {
if (root nullptr) return true;
return abs(deepth(root->left) – deepth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
private:
int deepth(TreeNode* root){
if (root nullptr) return 0;
return max(deepth(root->left), deepth(root->right)) + 1;
}
};递归判断左右子树的高度，并且左右子树的高度差<=1 ，如果所有子树都平衡，返回true

0 赞同 0 条回复

mpweixin用户普通 2024年3月7日上午10:55

public boolean isBalanced(TreeNode root) {
if(root null) return true;
return Math.abs(depth(root.left)-depth(root.right))<=1 && isBalanced(root.left)&&isBalanced(root.right);
}
public int depth(TreeNode root){
if(root null) return 0;
return Math.max(depth(root.left),depth(root.right))+1;
}
思路：思路是构造一个获取当前子树的深度的函数 depth(root) ，通过比较某子树的左右子树的深度差 abs(depth(root.left) – depth(root.right)) <= 1 是否成立，来判断某子树是否是二叉平衡树。若所有子树都平衡，则此树平衡。

0 赞同 0 条回复

Yuki 永久会员 2024年3月7日上午10:46

打卡
https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/solutions/2672403/pan-duan-avl-by-yukislab-m5de

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月7日上午9:33

打卡

class Solution {
public:
    // 递归，然后在回溯的过程中，求出每个子树的左右子树的深度，并判断该子树是否是AVL树，若不是则返回-1，函数结束。
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        int leftDepth = maxDepth(root->left);
        if(leftDepth == -1) return -1;
        int rightDepth = maxDepth(root->right);
        if(rightDepth == -1) return -1;
        if(abs(leftDepth - rightDepth) > 1) return -1;
        return max(leftDepth, rightDepth) + 1;

    }

    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        return maxDepth(root) != -1;

    }
};


class Solution {
public:
    int getDepth(TreeNode* root) {
        if(!root) return 0;
        return max(getDepth(root->left), getDepth(root->right)) + 1;
   }

    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        return abs(getDepth(root->left) - getDepth(root->right)) <= 1 
                && isBalanced(root->left) && isBalanced(root->right);
    }
};

0 赞同 0 条回复

紫芝普通 2024年3月7日上午9:13

思路：定一个函数：int isBal(Node* root), 然后判断每个节点，如果为空，则返回0；不为空时，递归计算左右子节点的高度，然后计算高度差是否小于等于1，如果是，则返回max(left, right)+1；否则返回-1。如果任一子节点返回-1，则该节点返回-1. -1表示不满足平衡二叉树。

“`c++
/**
* 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:
int isBal(TreeNode *root) {
if (root == nullptr) return 0;
int left = isBal(root->left);
int right = isBal(root->right);
if (left == -1 || right == -1) return -1;
if (abs(left-right) <= 1) return max(left, right) + 1; else return -1; } bool isBalanced(TreeNode* root) { return isBal(root) != -1; } }; ```

0 赞同 0 条回复

Yox 普通 2024年3月7日上午3:45

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def recur(root):
if not root:
return 0
left = recur(root.left)
if left -1:
return -1
right = recur (root.right)
if right -1:
return -1

        return max(left,right)+1 if abs(right - left) <=1 else -1
    return recur(root) != -1

双 o n

0 赞同 0 条回复

莫～慢～待普通 2024年3月7日上午12:53

class Solution {
public boolean isBalanced(TreeNode root) {
if(rootnull)
return true;
if(calculateDepth(root)-1)
return false;
return true;
}
public int calculateDepth(TreeNode root) {
if(rootnull)
return 0;
int leftdepth=calculateDepth(root.left);
if(leftdepth-1)
return -1;
int rightdepth=calculateDepth(root.right);
if(rightdepth-1)
return -1;
if(Math.abs(leftdepth-rightdepth)>1)
return -1;
return 1+Math.max(leftdepth,rightdepth);
}
}
利用树的深度判断平衡二叉树，-1标识非平衡二叉树

0 赞同 0 条回复

NULL 普通 2024年3月6日下午11:36

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null)return true;// 自顶向下递归
        return Math.abs(Depth(root.left) - Depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); 
    }
    public int Depth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(Depth(root.left),Depth(root.right)) + 1;
    }
}

0 赞同 0 条回复

Raphtalia. 普通 2024年3月6日下午11:29

法一：暴力版重复计算时间复杂度O（nlogn），空间复杂度O(logn)
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root nullptr) return true;
return abs(calculateDepth(root->left) – calculateDepth(root->right)) <= 1 && isBalanced(root->left) &&
isBalanced(root->right);
}

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

};
法二后序遍历计算
/**
* 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) {
return dfs(root) != -1;
}

int dfs(TreeNode* root) {
    if(root == nullptr) return 0;
    int l = dfs(root->left);
    if(l == -1) return -1;
    int r = dfs(root->right);
    if(r == -1) return -1;
    return abs(l - r) < 2 ? 1 + max(l, r) : -1;
}

};
时间复杂度O（n），空间复杂度O（LOGN）

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月6日下午11:26

class Solution {
    public boolean isBalanced(TreeNode root) {
        //注意点：空结点算平衡树
        if(root==null) return true;
        if(maxDepth(root)==-1) return false;
        return true;

    }

    public int maxDepth(TreeNode root){

        if(root==null) return 0;

        int left = maxDepth(root.left);
        if(left==-1) return -1;

        int right = maxDepth(root.right);
        if(right==-1) return -1;

        //注意点：最重要的这个条件不要忘了
        if(Math.abs(left-right)>1) return -1;

        return Math.max(left,right)+1;
    }
}

0 赞同 0 条回复

机电皮怪永久会员 2024年3月6日下午11:23

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

“`C++
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root == nullptr)
{
return true;
}

    int left = DFS(root->left);
    int right = DFS(root->right);

    if(abs(left - right) > 1)
    {
        return false;
    }
    return isBalanced(root->left) && isBalanced(root->right);
}

//DFS
int DFS(TreeNode* root)
{
    if(root == nullptr)
    {
        return 0;
    }
    int res1 = DFS(root->left) + 1;
    int res2 = DFS(root->right) + 1;

    return res1 > res2 ? res1 : res2;
}

};

“`

0 赞同 0 条回复

Free 普通 2024年3月6日下午9:07

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

    int getdepth(TreeNode* root)
    {
        if(root == nullptr)
            return 0;
        int leftdepth = getdepth(root->left) + 1;
        int rightdepth = getdepth(root->right) + 1;
        return max(leftdepth, rightdepth);
    }
};

时间 nlogn 空间 On

0 赞同 0 条回复

言之命至普通 2024年3月6日下午8:26

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

    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return Math.max(left, right) + 1;
    }
}

时间 nlogn 空间 On

0 赞同 0 条回复

王位詮釋普通 2024年3月6日下午8:25

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        if(Math.abs(Depth(root.left)-Depth(root.right))>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    public int Depth(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftDepth = Depth(root.left);
        int rightDepth = Depth(root.right);
        return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
    }
}
思路：获取深度，对比子树高度，如果两者高度差超过1那就不是平衡二叉树
这个代码效率不行，打败50%，得看下别的实现思路
时间复杂度：O(n2)

0 赞同 0 条回复

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

共以下 36 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

# 回答此问题取消回复

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

共以下 36 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

# 回答此问题 取消回复

# 回答此问题取消回复