android开发实战 Springboot 动态条形图 elasticsearch jboss nosql smtp usb 百度seo关键词 vue数据绑定 matlab对数函数 idea导入多个项目 java时间戳 python开发安卓应用 ubuntu显示隐藏文件夹 mysql时间戳转日期 python对象 python分析 java自学教程 java中泛型 java遍历 java生成文件 java连接sql数据库 java日期转时间戳 php实例 java游戏制作 磁盘分区软件 微信客户管理系统 黑白照片一键变彩色 lol设置 手机主题之家 微信彩色字 cad视口旋转 俄罗斯方块代码 拳皇2005出招表 igfxpers cad文件 鼠标速度怎么调 斐讯k3刷机 召唤加点90刷图加点
当前位置: 首页 > 学习教程  > 编程语言

「leetcode」110.平衡二叉树

2020/10/8 20:32:44 文章标签:

平不平衡看高度,注意不是深度。110.平衡二叉树 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,…

平不平衡看高度,注意不是深度。

110.平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

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

 

 

返回 true 。

示例 2:

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

 

 

返回 false 。

题外话

咋眼一看这道题目和二叉树:看看这些树的最大深度很像,其实有很大区别。

这里强调一波概念:

  • 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数。
  • 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数。

但leetcode中强调的深度和高度很明显是按照节点来计算的,如图:

 

 

关于根节点的深度究竟是1 还是 0,不同的地方有不一样的标准,leetcode的题目中都是以节点为一度,即根节点深度是1。但维基百科上定义用边为一度,即根节点的深度是0,我们暂时以leetcode为准(毕竟要在这上面刷题)。

因为求深度可以从上到下去查 所以需要前序遍历(中左右),而高度只能从下到上去查,所以只能后序遍历(左右中)

有的同学一定疑惑,为什么二叉树:看看这些树的最大深度中求的是二叉树的最大深度,也用的是后序遍历。

「那是因为代码的逻辑其实是求的根节点的高度,而根节点的高度就是这颗树的最大深度,所以才可以使用后序遍历。」

在二叉树:看看这些树的最大深度中,如果真正求取二叉树的最大深度,代码应该写成如下:(前序遍历)

class Solution {
public:
    int result;
    void getDepth(TreeNode* node, int depth) {
        result = depth > result ? depth : result; // 中

        if (node->left == NULL && node->right == NULL) return ;

        if (node->left) { // 左
            depth++;    // 深度+1
            getDepth(node->left, depth);
            depth--;    // 回溯,深度-1
        }
        if (node->right) { // 右
            depth++;    // 深度+1
            getDepth(node->right, depth);
            depth--;    // 回溯,深度-1
        }
        return ;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == 0) return result;
        getDepth(root, 1);
        return result;
    }
};

「可以看出使用了前序(中左右)的遍历顺序,这才是真正求深度的逻辑!」

注意以上代码是为了把细节体现出来,简化一下代码如下:

class Solution {
public:
    int result;
    void getDepth(TreeNode* node, int depth) {
        result = depth > result ? depth : result; // 中
        if (node->left == NULL && node->right == NULL) return ;
        if (node->left) { // 左
            getDepth(node->left, depth + 1);
        }
        if (node->right) { // 右
            getDepth(node->right, depth + 1);
        }
        return ;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == 0) return result;
        getDepth(root, 1);
        return result;
    }
};

本题思路

递归

此时大家应该明白了既然要求比较高度,必然是要后序遍历。

递归三步曲分析:

  1. 明确递归函数的参数和返回值

参数的话为传入的节点指针,就没有其他参数需要传递了,返回值要返回传入节点为根节点树的深度。

那么如何标记左右子树是否差值大于1呢。

如果当前传入节点为根节点的二叉树已经不是二叉平衡树了,还返回高度的话就没有意义了。

所以如果已经不是二叉平衡树了,可以返回-1 来标记已经不符合平衡树的规则了。

代码如下:

// -1 表示已经不是平衡二叉树了,否则返回值是以该节点为根节点树的高度
int getDepth(TreeNode* node)
  1. 明确终止条件

递归的过程中依然是遇到空节点了为终止,返回0,表示当前节点为根节点的高度为0

代码如下:

if (node == NULL) {
    return 0;
}
  1. 明确单层递归的逻辑

如何判断当前传入节点为根节点的二叉树是否是平衡二叉树呢,当然是左子树高度和右子树高度相差。

分别求出左右子树的高度,然后如果差值小于等于1,则返回当前二叉树的高度,否则则返回-1,表示已经不是二叉树了。

代码如下:

int leftDepth = depth(node->left); // 左
if (leftDepth == -1) return -1;     
int rightDepth = depth(node->right); // 右
if (rightDepth == -1) return -1;

int result;
if (abs(leftDepth - rightDepth) > 1) {  // 中
    result = -1;
} else {
    result = 1 + max(leftDepth, rightDepth); // 以当前节点为根节点的最大高度
}

return result;

代码精简之后如下:

int leftDepth = getDepth(node->left);
if (leftDepth == -1) return -1;     
int rightDepth = getDepth(node->right);
if (rightDepth == -1) return -1;
return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth);

此时递归的函数就已经写出来了,这个递归的函数传入节点指针,返回以该节点为根节点的二叉树的高度,如果不是二叉平衡树,则返回-1。

getDepth整体代码如下:

int getDepth(TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    int leftDepth = getDepth(node->left);
    if (leftDepth == -1) return -1;
    int rightDepth = getDepth(node->right);
    if (rightDepth == -1) return -1;
    return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth);
}

最后本题整体递归代码如下:

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度,如果不是二叉搜索树了则返回-1
    int getDepth(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int leftDepth = getDepth(node->left);
        if (leftDepth == -1) return -1; // 说明左子树已经不是二叉平衡树
        int rightDepth = getDepth(node->right);
        if (rightDepth == -1) return -1; // 说明右子树已经不是二叉平衡树
        return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth);
    }
    bool isBalanced(TreeNode* root) {
        return getDepth(root) == -1 ? false : true; 
    }
};

迭代

在二叉树:看看这些树的最大深度中我们可以使用层序遍历来求深度,但是就不能直接用层序遍历来求高度了,这就体现出求高度和求深度的不同。

本题的迭代方式可以先定义一个函数,专门用来求高度。

这个函数通过栈模拟的后序遍历找每一个节点的高度(其实是通过求传入节点为根节点的最大深度来求的高度)

代码如下:

// cur节点的最大深度,就是cur的高度
int getDepth(TreeNode* cur) {
    stack<TreeNode*> st;
    if (cur != NULL) st.push(cur);
    int depth = 0; // 记录深度
    int result = 0;
    while (!st.empty()) {
        TreeNode* node = st.top();
        if (node != NULL) {
            st.pop();
            st.push(node);                          // 中
            st.push(NULL);
            depth++;
            if (node->right) st.push(node->right);  // 右
            if (node->left) st.push(node->left);    // 左

        } else {
            st.pop();
            node = st.top();
            st.pop();
            depth--;
        }
        result = result > depth ? result : depth;
    }
    return result;
}

然后再用栈来模拟前序遍历,遍历每一个节点的时候,再去判断左右孩子的高度是否符合,代码如下:

bool isBalanced(TreeNode* root) {
    stack<TreeNode*> st;
    if (root == NULL) return true;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();                       // 中
        st.pop();
        if (abs(getDepth(node->left) - getDepth(node->right)) > 1) { // 判断左右孩子高度是否符合
            return false;
        }
        if (node->right) st.push(node->right);           // 右(空节点不入栈)
        if (node->left) st.push(node->left);             // 左(空节点不入栈)
    }
    return true;
}

整体代码如下:

class Solution {
private:
    int getDepth(TreeNode* cur) {
        stack<TreeNode*> st;
        if (cur != NULL) st.push(cur);
        int depth = 0; // 记录深度
        int result = 0;
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                st.push(node);                          // 中
                st.push(NULL);
                depth++;
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                depth--;
            }
            result = result > depth ? result : depth;
        }
        return result;
    }

public:
    bool isBalanced(TreeNode* root) {
        stack<TreeNode*> st;
        if (root == NULL) return true;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            if (abs(getDepth(node->left) - getDepth(node->right)) > 1) {
                return false;
            }
            if (node->right) st.push(node->right);           // 右(空节点不入栈)
            if (node->left) st.push(node->left);             // 左(空节点不入栈)
        }
        return true;
    }
};

当然此题用迭代法,其实效率很低,因为没有很好的模拟回溯的过程,所以迭代法有很多重复的计算。

虽然理论上所有的递归都可以用迭代来实现,但是有的场景难度可能比较大。

「例如:都知道回溯法其实就是递归,但是很少人用迭代的方式去实现回溯算法!」

因为对于回溯算法已经是非常复杂的递归了,如果在用迭代的话,就是自己给自己找麻烦,效率也并不一定高。

总结

通过本题可以了解求二叉树深度 和 二叉树高度的差异,求深度适合用前序遍历,而求高度适合用后序遍历。

本题迭代法其实有点复杂,大家可以有一个思路,也不一定说非要写出来。

但是递归方式是一定要掌握的!

本文:https://github.com/youngyangyang04/leetcode-master​已经收录,里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图,可以fork到自己仓库,有空看一看一定会有所收获,如果对你有帮助也给一个star支持一下吧!

我的B站(里面有我讲解的算法视频以及编程相关知识):https://space.bilibili.com/525438321

我是程序员Carl,哈工大师兄,先后在腾讯和百度从事技术研发多年,利用工作之余重刷leetcode,更多     精彩算法文章尽在:   代码随想录,关注后,回复「Java」「C++」「python」「简历模板」等等,有我整理多年的学习资料,可以加我    微信,备注「个人简介」+「组队刷题」,拉你进入刷题群(无任何广告,纯个人分享),每天一道经典题目分析,我选的每一道题目都不是孤立的,而是由浅入深一脉相承的,如果跟住节奏每篇连续着看,定会融会贯通。
代码随想录 CSDN认证博客专家 C++ 算法与数据结构 后端研发技术栈
我是程序员Carl,ACM/ICPC亚洲区域赛铜奖获得者,哈工大计算机硕士毕业,先后就职于腾讯和百度。微信公众号:「代码随想录」,希望结合自己多年的实践经验,把算法讲的更清楚。

本文链接: http://www.dtmao.cc/news_show_250349.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?