AcWing 72. 平衡二叉树

思路一：求每个节点的左右子树深度，根据深度差判断，直到叶子节点结束，效率不够高，每个节点都要用两次计算深度的递归函数

思路二：从叶子节点开始，计算深度差，一旦有深度差大于1的，就直接返回0，也不用管上面的深度是不是正确了，毕竟我们只需要true和false两种状态，省略了很多次深度的计算

思路二的代码

class Solution {

boolean balanced=true;

public boolean isBalanced(TreeNode root) {

getDepth(root);

return balanced;

}

int getDepth(TreeNode root){

if(root==null) return 0;

int left=getDepth(root.left);

if(!balanced) return 0;

int right=getDepth(root.right);

if(!balanced) return 0;

if(Math.abs(left-right)>1) {

balanced=false;

return 0;

}

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

}

}

发布于 2020-02-16

AcWing 72. Go 题解　平衡二叉树

Talke is cheap.

/**

* Definition for a binary tree node.

* type TreeNode struct {

* Val int

* Left *TreeNode

* Right *TreeNode

* }

*/

func isBalanced(root *TreeNode) bool {

return isBalan(root) != -1

}

func isBalan(root *TreeNode) int {

if root == nil {

return 0

}

left := isBalan(root.Left)

right := isBalan(root.Right)

if left == -1 || right == -1 || left - right > 1 || left - right < -1 {

return -1

}

if left > right {

return left + 1

}

return right + 1

}

发布于 2020-02-16

AcWing 72. 平衡二叉树

C++几行直接解决

算法

直接用高度h，平衡二叉树递归满足1、左右子树是平衡的

2、左子树-右子树高度的绝对值<2

时间复杂度

o(n)

/**

* 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) return true;

return isBalanced(root->left)&&isBalanced(root->right)&&abs(h(root->left)-h(root->right))<2;

}

int h(TreeNode *bt)

{

if(!bt)return 0;

return max(h(bt->left),h(bt->right))+1;

}

};

发布于 2020-02-16

AcWing 72. 平衡二叉树

题目描述

blablabla

算法1

(暴力枚举) $O(n)$

将求深度的代码稍作修改，不重复求深度。

时间复杂度分析：因为只遍历结点一次，所以最坏情形为O(n)

C++ 代码

class Solution {

public:

bool isBalanced(TreeNode* root) {

/*

unit test

root is nil

root not nil, left is nil, right is nil

root not nil, left not nil, right nil.

*/

int height=dfs(root);

if(height>=0) return true;

else return false;

}

// 当非平衡时，return -1; 平衡时，return high;

// 首先判断左子树平衡与否，再判断右子树平衡与否，在判断整棵树平衡与否；

int dfs(TreeNode *root){

if(!root) return 0;

int left=dfs(root->left);

if(left<0) return -1;

int right=dfs(root->right);

if(right<0) return -1;

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

return max(left,right)+1;

}

};

发布于 2020-02-16

AcWing 72. 平衡二叉树

题目描述

输入二叉树的根节点,判断该树是不是平衡二叉树

样例

输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示，

5

/ \

7 11

/ \

12 9

输出：true

算法

递归

可以结合二叉树深度的方法,递归判断每一个结点的左右子树是否都满足深度相差小于1的条件

C++ 代码

class Solution {

public:

#计算树的深度

int treeDepth(TreeNode* root){

if(!root) return 0;

return max(treeDepth(root->left),treeDepth(root->right))+1;

}

bool isBalanced(TreeNode* root) {

if(!root) return true;

int left = treeDepth(root->left);

int right = treeDepth(root->right);

#判断左右子树是否满足条件,然后如果满足条件,判断子树的子树是否满足条件

if(abs(left-right)<=1) return isBalanced(root->left)&&isBalanced(root->right);

#如果不满足条件直接返回false

else return false;

}

};

发布于 2020-02-16

AcWing 72. 平衡二叉树--Java代码

算法1

(递归)

在上一题的基础上，得出左右子树的深度，然后求差，如果大于1，则返回false;

然后递归每个节点，这个算法的弊端是，每个节点递归两次

Java 代码

class Solution {

public boolean isBalanced(TreeNode root) {

if(root==null){

return true;

}

int left = treeDepth(root.left);

int right = treeDepth(root.right);

int diff = left-right;

if(Math.abs(diff)>1)

return false;

return isBalanced(root.left)&&isBalanced(root.right);

}

public int treeDepth(TreeNode root) {

if(root==null){

return 0;

}

int left = treeDepth(root.left);

int right = treeDepth(root.right);

return left>right?left+1:right+1;

}

}

算法2

(后序遍历) $O(n)$

后续遍历，得到的左右子树的高度差立即进行判断即可

Java 代码

class Solution {

private boolean isBalanced=true;

public boolean isBalanced(TreeNode root) {

getDepth(root);

return isBalanced;

}

public int getDepth(TreeNode root){

if(root==null)

return 0;

int left=getDepth(root.left);

int right=getDepth(root.right);

if(Math.abs(left-right)>1){

isBalanced=false;

}

return right>left ?right+1:left+1;

}

}

发布于 2020-02-16

AcWing 72. 平衡二叉树

题目描述

本题的思路就是对于每一个节点，依次递归求出每个节点的左子树高度和右子树高度，如果左右子树的高度之差大于1.就说明该二叉树非平衡。对于每一次返回值此处需要强调下，是返回该节点左右子树中的最大值，第二点需要强调的是对于root节点，只用判断其左右子树的高度差是否大于1即可，不需要加上root的高度。

算法1

(dfs) $O(n)$

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 {

public:

bool ans = true;

bool isBalanced(TreeNode* root) {

if(!root) return true;

int leftDepth = dfs(root->left);

int rightDepth = dfs(root->right);

if (abs(leftDepth - rightDepth) <= 1 && ans) return true;

return false;

}

int dfs(TreeNode* root)

{

if(!root) return 0;

if(ans == false) return 0;

int leftDepth = dfs(root->left) + 1;

int rightDepth = dfs(root->right) + 1;

if(abs(leftDepth - rightDepth) <= 1) ans = true;

else ans = false;

return max(leftDepth, rightDepth);

}

};

发布于 2020-02-16

AcWing 72. 平衡二叉树

题目描述

blablabla

样例

blablabla

算法1

blablabla

时间复杂度分析：blablabla

C++ 代码

class Solution {

public boolean isBalanced(TreeNode root) {

return isBalanced1(root).flag;

}

static class Res{

int h;

boolean flag;

public Res(int h, boolean flag) {

this.h = h;

this.flag = flag;

}

}

public Res isBalanced1(TreeNode root) {

if (root==null){

return new Res(0,true);

}

Res a=isBalanced1(root.left);

Res b=isBalanced1(root.right);

if (a.flag&&b.flag)

return new Res(Math.max(a.h,b.h)+1,Math.abs(a.h-b.h)<=1);

return new Res(-1,false);

}

}

发布于 2020-02-16

AcWing 72. python看我

题目描述

blablabla

样例

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution(object):

ans = True

def isBalanced(self, root):

"""

:type root: TreeNode

:rtype: bool

"""

if not root:

return True

self.helper(root)

return self.ans

def helper(self, root):

if not root:

return 0

left = self.helper(root.left)

right = self.helper(root.right)

if abs(right - left) > 1:

self.ans = False

return right + 1 if right > left else left + 1

发布于 2020-02-16