美团面试官:你对后序遍历一无所知

2021年11月24日 阅读数:3
这篇文章主要向大家介绍美团面试官:你对后序遍历一无所知,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

 

https://labuladong.gitee.io/algo/2/18/27/java

 

读完本文,你不只学会了算法套路,还能够顺便去 LeetCode 上拿下以下题目:git

1373.二叉搜索子树的最大键值和(困难)面试

———–算法

其实二叉树的题目真的不难,无非就是前中后序遍历框架来回倒嘛,可是对于有的题目,不一样的遍历顺序时间复杂度不一样。数组

以前面试美团,就遇到一道二叉树算法题,当时我是把解法写出来了,面试官说若是用后序遍历,时间复杂度能够更低。框架

本文就来分析一道相似的题目,经过二叉树的后序遍历,来大幅下降算法的复杂度。函数

手把手刷二叉树第一期 说过二叉树相关题目最核心的思路是明确当前节点须要作的事情是什么。oop

咱们再看看后序遍历的代码框架:优化

void traverse(TreeNode root) { traverse(root.left); traverse(root.right); /* 后序遍历代码的位置 */ /* 在这里处理当前节点 */ } 

看这个代码框架,你说后序遍历何时出现呢?this

若是当前节点要作的事情须要经过左右子树的计算结果推导出来,就要用到后序遍历。

不少时候,后序遍历用得好,能够大幅提高算法效率。

咱们今天就要讲一个经典的算法问题,能够直观地体会到这一点。

这是力扣第 1373 题「二叉搜索子树的最大键值和」,函数签名以下:

int maxSumBST(TreeNode root); 

题目会给你输入一棵二叉树,这棵二叉树的子树中可能包含二叉搜索树对吧,请你找到节点之和最大的那棵二叉搜索树,返回它的节点值之和。

​二叉搜索树(简写做 BST)的性质不用我多介绍了吧,简单说就是「左小右大」,对于每一个节点,整棵左子树都比该节点的值小,​整棵右子树都比该节点的值大。

好比题目给了这个例子:

若是输入这棵二叉树,算法应该返回 20,也就是图中绿圈的那棵子树的节点值之和,由于它是一棵 BST,且节点之和最大。

那有的读者可能会问,根据 BST 的定义,有没有可能一棵二叉树中不存在 BST?

不会的,由于按照 BST 的定义,任何一个单独的节点确定是 BST,也就是说,再不济,二叉树最下面的叶子节点确定是 BST。

好比说若是输入下面这棵二叉树:

两个叶子节点 1 和 2 就是 BST,比较一下节点之和,算法应该返回 2。

好了,到这里,题目应该解释地很清楚了,下面咱们来分析一下这道题应该怎么作。

刚才说了,二叉树相关题目最核心的思路是明确当前节点须要作的事情是什么。

那么咱们想计算子树中 BST 的最大和,站在当前节点的视角,须要作什么呢?

一、我确定得知道左右子树是否是合法的 BST,若是这俩儿子有一个不是 BST,以我为根的这棵树确定不会是 BST,对吧。

二、若是左右子树都是合法的 BST,我得瞅瞅左右子树加上本身仍是不是合法的 BST 了。由于按照 BST 的定义,当前节点的值应该大于左子树的最大值,小于右子树的最小值,不然就破坏了 BST 的性质。

三、由于题目要计算最大的节点之和,若是左右子树加上我本身仍是一棵合法的 BST,也就是说以我为根的整棵树是一棵 BST,那我须要知道咱们这棵 BST 的全部节点值之和是多少,方便和别的 BST 争个高下,对吧。

根据以上三点,站在当前节点的视角,须要知道如下具体信息:

一、左右子树是不是 BST。

二、左子树的最大值和右子树的最小值。

三、左右子树的节点值之和。

只有知道了这几个值,咱们才能知足题目的要求,后面咱们会千方百计计算这些值。

如今能够尝试用伪码写出算法的大体逻辑:

// 全局变量,记录 BST 最大节点之和
int maxSum = 0;

/* 主函数 */
public int maxSumBST(TreeNode root) { traverse(root); return maxSum; } /* 遍历二叉树 */ void traverse(TreeNode root) { if (root == null) { return; } /******* 前序遍历位置 *******/ // 判断左右子树是否是 BST if (!isBST(root.left) || !isBST(root.right)) { goto next; } // 计算左子树的最大值和右子树的最小值 int leftMax = findMax(root.left); int rightMin = findMin(root.right); // 判断以 root 节点为根的树是否是 BST if (root.val <= leftMax || root.val >= rightMin) { goto next; } // 若是条件都符合,计算当前 BST 的节点之和 int leftSum = findSum(root.left); int rightSum = findSum(root.right); int rootSum = leftSum + rightSum + root.val; // 计算 BST 节点的最大和 this.maxSum = Math.max(maxSum, rootSum); /**************************/ // 递归左右子树 next: traverse(root.left); traverse(root.right); } /* 计算以 root 为根的二叉树的最大值 */ int findMax(TreeNode root) {} /* 计算以 root 为根的二叉树的最小值 */ int findMin(TreeNode root) {} /* 计算以 root 为根的二叉树的节点和 */ int findSum(TreeNode root) {} /* 判断以 root 为根的二叉树是不是 BST */ boolean isBST(TreeNode root) {} 

这个代码逻辑应该是不难理解的,代码在前序遍历的位置把以前的分析都实现了一遍。

其中有四个辅助函数比较简单,我就不具体实现了,其中只有判断合法 BST 的函数稍有技术含量,前文 二叉搜索树操做集锦 写过,这里就不展开了。

稍做分析就会发现,这几个辅助函数都是递归函数,都要遍历输入的二叉树,外加 traverse 函数自己的递归,能够说是递归上加递归,因此这个解法的复杂度是很是高的。

可是根据刚才的分析,像 leftMaxrootSum 这些变量又都得算出来,不然没法完成题目的要求。

咱们但愿既算出这些变量,又避免辅助函数带来的额外复杂度,鱼和熊掌全都要!

实际上是能够的,只要把前序遍历变成后序遍历,让 traverse 函数把辅助函数作的事情顺便作掉。

其余代码不变,咱们让 traverse 函数作一些计算任务,返回一个数组:

// 全局变量,记录 BST 最大节点之和
int maxSum = 0;

/* 主函数 */
public int maxSumBST(TreeNode root) { traverse(root); return maxSum; } // 函数返回 int[]{ isBST, min, max, sum} int[] traverse(TreeNode root) { int[] left = traverse(root.left); int[] right = traverse(root.right); /******* 后序遍历位置 *******/ // 经过 left 和 right 推导返回值 // 而且正确更新 maxSum 变量 /**************************/ } 

traverse(root) 返回一个大小为 4 的 int 数组,咱们暂且称它为 res,其中:

res[0] 记录以 root 为根的二叉树是不是 BST,若为 1 则说明是 BST,若为 0 则说明不是 BST;

res[1] 记录以 root 为根的二叉树全部节点中的最小值;

res[2] 记录以 root 为根的二叉树全部节点中的最大值;

res[3] 记录以 root 为根的二叉树全部节点值之和。

其实这就是把以前分析中说到的几个值放到了 res 数组中,最重要的是,咱们要试图经过 left 和 right 正确推导出 res 数组。

直接看代码实现吧:

int[] traverse(TreeNode root) {
    // base case
    if (root == null) {
        return new int[] { 1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0 }; } // 递归计算左右子树 int[] left = traverse(root.left); int[] right = traverse(root.right); /******* 后序遍历位置 *******/ int[] res = new int[4]; // 这个 if 在判断以 root 为根的二叉树是否是 BST if (left[0] == 1 && right[0] == 1 && root.val > left[2] && root.val < right[1]) { // 以 root 为根的二叉树是 BST res[0] = 1; // 计算以 root 为根的这棵 BST 的最小值 res[1] = Math.min(left[1], root.val); // 计算以 root 为根的这棵 BST 的最大值 res[2] = Math.max(right[2], root.val); // 计算以 root 为根的这棵 BST 全部节点之和 res[3] = left[3] + right[3] + root.val; // 更新全局变量 maxSum = Math.max(maxSum, res[3]); } else { // 以 root 为根的二叉树不是 BST res[0] = 0; // 其余的值都不必计算了,由于用不到 } /**************************/ return res; } 

这样,这道题就解决了,traverse 函数在遍历二叉树的同时顺便把以前辅助函数作的事情都作了,避免了在递归函数中调用递归函数,时间复杂度只有 O(N)。

你看,这就是后序遍历的妙用,相对前序遍历的解法,如今的解法不只效率高,并且代码量少,比较优美。

那确定有读者问,后序遍历这么好,是否是就应该尽量多用后序遍历?

其实也不是,主要是看题目,就比如 BST 的中序遍历是有序的同样。

这道题为何用后序遍历呢,由于咱们须要的这些变量都是能够经过后序遍历获得的。

你计算以 root 为根的二叉树的节点之和,是否是能够经过左右子树的和加上 root.val 计算出来?

你计算以 root 为根的二叉树的最大值/最小值,是否是能够经过左右子树的最大值/最小值和 root.val 比较出来?

你判断以 root 为根的二叉树是否是 BST,是否是得先判断左右子树是否是 BST?是否是还得看看左右子树的最大值和最小值?

文章开头说过,若是当前节点要作的事情须要经过左右子树的计算结果推导出来,就要用到后序遍历。

由于以上几点均可以经过后序遍历的方式计算出来,因此这道题使用后序遍历确定是最高效的。

以个人刷题经验,咱们要尽量避免递归函数中调用其余递归函数,若是出现这种状况,大几率是代码实现有瑕疵,能够进行相似本文的优化来避免递归套递归。

_____________