LeetCode 二叉树问题小总结

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

LeetCode 二叉树问题小总结

作者 | P.yh

来源 | 五分钟学算法

导言

LeetCode 上面的二叉树问题一般可以看成是简单的深度优先搜索问题,一般的实现方式是使用递归,也会有非递归的实现方法,这边文章主要介绍一下解决二叉树问题的几个常规方法和思路,然后会给一个从递归转换到非递归的小技巧。

两个通用方法和思路

拿到一道二叉树的问题,多半是需要你遍历这个树,只不过是在遍历的过程中,不同的题目要求你做的计算不一样。

这里有两个遍历方法,自顶向下的递归遍历,以及自底向上的分治

两种方法都用到了递归,在代码实现上面,差别不是特别大,但是思路却截然相反,我们拿树的中序遍历这道题目来作为示例。

事实上,在 LeetCode 以及面试过程中,对二叉树的遍历考察的非常多,所以,请务必理解二叉树的前、中、后序三种遍历方式

花几分钟借助下面三个动画彻底理解一下二叉树遍历的过程吧。

LeetCode 二叉树问题小总结

LeetCode 二叉树问题小总结


LeetCode 二叉树问题小总结

自顶向下的递归遍历

public List<Integer> inorderTraversal(TreeNode root{
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    helper(root, result);

    return result;
}

private void helper(TreeNode root, List<Integer> result{
    if (root == null) {
        return;
    }

    helper(root.left, result);
    result.add(root.val);
    helper(root.right, result);
}

代码非常的简短,上面代码的重心全放在了 helper 函数上,这个函数没有返回值,它做的事情也非常的简单,就是去到对应的树节点,然后把节点的值加到 result 中。

这里我们要求的是树的 中序遍历,因此,我们要先去到当前树节点的左边,把左边所有的节点的值放到 result 中,才会继续放当前树节点,放完当前树节点的值后,我们会去到右边进行同样的操作。

对于这种实现方法其实有点类似于循环遍历,只不过循环遍历只作用于数组还有链表这样的线性结构,对于树的话,这里我们采用了递归的方式去遍历,你可以想象成一个小人在一棵树上面游走,他的目的是按顺序去记录树的节点值。

自底向上的分治

public List<Integer> inorderTraversal(TreeNode root{
    List<Integer> result = new ArrayList<>();

    if (root == null) {
        return result;
    }

    result.addAll(inorderTraversal(root.left));
    result.add(root.val);
    result.addAll(inorderTraversal(root.right));

    return result;
}

同一个问题,再来看看我们之前提到的另外一种思路实现。

这里我们也使用了递归,但是这次的递归函数是有返回值的,而且你也可以看到的是,我们没有将保存结果的 list 传入函数。

正因为是自底向上,所以对于一个树节点来说,它这里会知道它子节点的返回值,也就是子节点的记录结果,在它这里会把左右子节点的结果,和它自己本身的结果汇总,然后将汇总的结果返回给上一层节点。

和之前的递归遍历的思路相比的话,代码实现上面的区别可能就是,是将 result list 放在参数中,还是放在返回值中,但是思考方向是截然相反的。

这里就不好用之前的 “小人游走” 来解释了。

更好的解释方式是公司职位,这里你可以想象每个树节点就是企业里面的一个人,或者说是一个职位,最上面的 root 节点就是企业的 CEO,往下是副总裁,然后再往下是总监,总监往下是经理,。。。在副总裁这里,他会向他下面的两个总监要结果,在他这里把两个总监返回的结果汇总,然后上报给 CEO,他不会去关注经理的结果,底层员工的结果,在他这里,只关心下一层和上一层。

这两种方法没有好坏之分,有的题目使用自顶向下递归遍历的方式会比较直接一点,比如求最大最小值,有些题目则使用自底向上分治的方式会比较好一些,比如说 subtree 的问题。对于不同的题目,我们需要选择不同的方法,但是思考方式可以考虑从这两个方向去思考。

一般来说,二叉树问题的时间复杂度都是 O(n) ,这个时间复杂的怎么理解呢?你可以看成是在每个树节点上的操作的时间复杂度是 O(1),但是要遍历所有的节点,因此 O(1) * n = O(n)。


递归转非递归


对于树的问题,我们也可以使用非递归的方式求解,其实任何一个递归的解法,都可以转换为非递归,而且就性能和稳定性来说的话,非递归的方式要比递归来的好。

但是问题是,非递归代码不是那么好写,通常来说递归的解法会简洁不少,因此在面试中,面试官通常会让写递归。

但是,有些时候,面对一个简单的问题,有些面试官会让你写出非递归的解法,比如上面的中序遍历的例子,相比于递归的简洁一致,非递归的实现可能每个人写出来都会略有不同,我记得我第一次试着把递归写成非递归是非常痛苦的,完全没有头绪。

我这里给出了一个递归转非递归的通用方法,不仅仅适用于树的问题,对于任何的递归问题都适用,这个方法也是我在 LeetCode 的 discuss 中看到的,还是拿上面中序遍历作为例子,之前我们的代码实现:

public List<Integer> inorderTraversal(TreeNode root{
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    helper(root, result);

    return result;
}

private void helper(TreeNode root, List<Integer> result{
    if (root == null) {
        return;
    }

    helper(root.left, result); // line 0
    result.add(root.val);      // line 1
    helper(root.right, result);// line 2
}

你可以看到,我在 helper 函数最后 3 行代码标上了序号,后面的非递归实现的程序中会用到,这里我们主要是要实现 helper 函数中的东西。

非递归代码如下:

public List<Integer> inorderTraversal(TreeNode root{
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Stack<Integer> systemStack = new Stack<>(); // 表示函数进度
    Stack<TreeNode> paramStack = new Stack<>(); // 表示函数输入参数

    systemStack.push(0);
    paramStack.push(root);

    while (!systemStack.isEmpty()) {
        int curLine = systemStack.pop();
        TreeNode curParam = paramStack.peek();

        // 提前将当前进度后移,因为后面可能会有其他函数入栈
        systemStack.push(curLine + 1);

        if (curLine == 0) {
            if (curParam.left != null) {
                systemStack.push(0);
                paramStack.push(curParam.left);                    
            }
        } else if (curLine == 1) {
            result.add(curParam.val);
        } else if (curLine == 2) {
            if (curParam.right != null) {
                systemStack.push(0);
                paramStack.push(curParam.right);
            }
        } else {
            systemStack.pop();
            paramStack.pop();
        }
    }

    return result;
}

一般来说,用非递归写递归,都需要用到一个数据结构-栈

这个好解释,递归的解法是利用了系统中提供的函数栈,非递归我们需要手动创建这么一个数据结构,但是你可能会问的是,这里为什么要用到两个栈?

你可以这样认为,一个栈用来表示函数的运行进度,里面的元素表示此时该函数运行到了第几行代码,另一个栈用来记录函数的传入参数,当然你也可以把这两个栈合成一个栈,里面装的是封装好的对象。

这里为了解释起来清晰直观,就用两个栈。

首先,根据之前的递归解法,我们最开始是把 root 传入 helper 函数,因此这时我们也把 root 加入函数栈,另外一个表示函数进度的栈往里面添加 0,表示当前函数运行到了第 0 行,然后就是 while 循环里面的东西,while 循环一开始我们就获取当前函数的输入参数和进度,然后根据函数的进度去看需要执行哪一段代码,因为有的代码会继续往栈里面添加函数,因此,我们需要提前把函数进度往后移动,你可以对应之前的递归的代码和我标的序号,你可以看到,整个 if-else if…else 部分就表示了之前的递归函数中的代码,只不过这里我们需要根据函数的进度去判断它要执行哪一行。

使用这种方法后,递归转非递归只需要往上套就行,不需要单独分析。


LeetCode 二叉树问题小总结

有热门推荐👇


1.程序员全球最厉害的 14 位程序员

2.【GitHub我在 GitHub 上看到了一个丧心病狂的开源项目!

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!


LeetCode 二叉树问题小总结


本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » LeetCode 二叉树问题小总结

我还会在以下平台发布内容

GitHub 哔哩哔哩