vlambda博客
学习文章列表

【每日算法】平衡二叉树

蓝字


【每日算法】平衡二叉树
【每日算法】平衡二叉树

描述

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树

平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

注:我们约定空树是平衡二叉树。

示例1输入:{1,2,3,4,5,6,7}返回值:true



【每日算法】平衡二叉树

题解

这是一篇针对初学者的题解,用两种方法解决。
知识点:树,递归
难度:一星


题解

方法一:自顶向下

判断一个数是否为平衡二叉树。平衡二叉树是左子树的高度与右子树的高度差的绝对值小于等于1,同样左子树是平衡二叉树,右子树为平衡二叉树。

根据定义,如果我们能够求出以每个结点为根的树的高度,然后再根据左右子树高度差绝对值小于等于1,,就可以判断以每个结点为根的树是否满足定义。
我们可以用hash<TreeNode*, int>来存以每个结点的树的高度。
代码如下:


1

2

3

4

5

6

7

8

map<TreeNode*, int> hs;

int depth(TreeNode *root) {

    if (!root) return 0;

    if (hs.find(root) != hs.end()) return hs[root];

    int ldep = depth(root->left);

    int rdep = depth(root->right);

    return hs[root] = max(ldep, rdep) + 1;

}

然后再用先序遍历:根节点、左子树、右子树来判断以每个结点为根的树是否满足条件。
代码如下:


1

2

3

4

5

bool judge(TreeNode *root) {

    if (!root) return true;

    return abs(hs[root->left] - hs[root->right]) <= 1 &&

    judge(root->left) && judge(root->right);

}

最后的代码为:


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution {

public:

    map<TreeNode*, int> hs;

    int depth(TreeNode *root) {

        if (!root) return 0;

        if (hs.find(root) != hs.end()) return hs[root];

        int ldep = depth(root->left);

        int rdep = depth(root->right);

        return hs[root] = max(ldep, rdep) + 1;

    }

    bool judge(TreeNode *root) {

        if (!root) return true;

        return abs(hs[root->left] - hs[root->right]) <= 1 &&

        judge(root->left) && judge(root->right);

    }

    bool IsBalanced_Solution(TreeNode* root) {

        depth(root);

        return judge(root);

    }

};

时间复杂度:O(N)
空间复杂度:O(N)

方法二:自底向上

方法一是先求出以每个结点为根的树的高度,然后再判断,其实可以直接再求高度的同时,直接判断即可。
利用后序遍历:左子树、右子树、根节点,可以先递归到叶子节点,然后在回溯的过程中来判断是否满足条件。
求树的高度的代码为:


1

2

3

4

5

6

int depth(TreeNode *root) {

    if (!root) return 0;

    int ldep = depth(root->left);

    int rdep = depth(root->right);

    return max(ldep, rdep) + 1;

}

然后对上述代码加以改造,如果不满足平衡二叉树的定义,则返回-1,并且如果左子树不满足条件了,直接返回-1,右子树也是如此,相当于剪枝,加速结束递归。
代码如下:


1

2

3

4

5

6

7

8

9

10

int depth(TreeNode *root) {

    if (!root) return 0;

    int ldep = depth(root->left);

    if (ldep == -1return -1;

    int rdep = depth(root->right);

    if (rdep == -1return -1;

    int sub = abs(ldep - rdep);

    if (sub > 1return -1;

    return max(ldep, rdep) + 1;

}

最后只需要判断depth(root)返回的是否为-1,如果是-1,则不是,否则,则是。
代码如下:


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution {

public:

    int depth(TreeNode *root) {

        if (!root) return 0;

        int ldep = depth(root->left);

        if (ldep == -1return -1;

        int rdep = depth(root->right);

        if (rdep == -1return -1;

        int sub = abs(ldep - rdep);

        if (sub > 1return -1;

        return max(ldep, rdep) + 1;

    }

    bool IsBalanced_Solution(TreeNode* root) {

        return depth(root) != -1;

    }

};

时间复杂度:O(N)
空间复杂度:O(N)


Java的方式
import java.lang.*;public class Solution { public boolean IsBalanced_Solution(TreeNode root) { if(root == null){ return true; } int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); if(Math.abs(leftHeight - rightHeight) > 1){ return false;  } return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right); } public int getHeight(TreeNode root){ if(root == null){ return 0; } int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); return 1 + (leftHeight > rightHeight ? leftHeight :rightHeight); }}

【每日算法】平衡二叉树
【每日算法】平衡二叉树



扫描关注

开启学习之路

BCS联盟


在看,传播技术之光。