算法 - 二叉树
导读:精读 要入门二叉树,就必须理解二叉树的三种遍历策略,分别是:前序遍历、中序遍历、后序遍历,这些都属于深度优先遍历。 所谓前中后,就是访问节点值在什么时机,其余时机按先左后右访问子节点。比如前序遍历,就是先访问值,再访问左右;后续遍历就是...
精读
要入门二叉树,就必须理解二叉树的三种遍历策略,分别是:前序遍历、中序遍历、后序遍历,这些都属于深度优先遍历。
所谓前中后,就是访问节点值在什么时机,其余时机按先左后右访问子节点。比如前序遍历,就是先访问值,再访问左右;后续遍历就是先访问左右,再访问值;中序遍历就是左,值,右。
用递归方式遍历树非常简单:
function visitTree(node: TreeNode) {
// 三选一:前序遍历
// console.log(node.val)
visitTree(node.left)
// 三选一:中序遍历
// console.log(node.val)
visitTree(node.right)
// 三选一:后序遍历
// console.log(node.val)
}
当然题目需要我们巧妙利用二叉树三种遍历的特性来解题,比如重建二叉树。
重建二叉树
重建二叉树是一道中等题,题目如下:
输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
先给你二叉树前序与中序遍历结果,让你重建二叉树,这种逆向思维的题目就难了不少。
仔细观察遍历特性可以看出,我们也许能推测出一些关键节点的位置,再通过数组切割递归一下就能解题。
前序遍历第一个访问的一定是根节点,因此 3 一定是根节点,然后我们在中序遍历找到 3,这样 左边就是所有左子树的中序遍历结果,右边就是所有右子树的中序遍历结果,我们只要再找到 左子树的前序遍历结果与右子树的前序遍历结果,就可以递归了,终止条件是左或右子树只有一个值,那样就代表叶子节点。
那么怎么找左右子树的前序遍历呢?上面例子中,我们找到了 3 的左右子树的中序遍历结果,由于前序遍历优先访问左子树,因此我们数一下中序遍历中,3 左边的数量,只有一个 9,那么我们从前序遍历的 3,9,20,15,7 在 3 之后推一位,那么 9 就是左子树前序遍历结果,9 后面的 20,15,7 就是柚子树的前序遍历结果。
最后只要递归一下就能解题了,我们将输入不断拆解为左右子树的的输入,直到达到终止条件。
解决此题的关键是,不仅要直到如何写前中后序遍历,还要知道前序遍历第一个节点是根节点,后序遍历最后一个节点是根节点,中序遍历以根节点为中心,左右分别是其左右子树,这几个重要延伸特征。
说完了反向,我们说正向,即递归一颗二叉树。
其实二叉树除了递归,还有一种常见的遍历方法是利用栈进行广度优先遍历,典型题目有从上到下打印二叉树。
从上到下打印二叉树
从上到下打印二叉树是一道简单题,题目如下:
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
这道题要求从左到右顺序打印,完全遵循广度优先遍历,我们可以在二叉树递归时,先不要急着读取值,而是按照左、中、右,遇到左右子树节点,就推入栈的末尾,利用 while 语句不断循环,直到栈空为止。
利用展开时追加到栈尾,并不断循环处理栈元素的方式非常优雅,而且符合栈的特性。
当然如果题目要求倒序打印,你就可以以 右、中、左 的顺序进行处理。
接下来看看深度优先遍历,典型题目是二叉树的深度。
二叉树的深度
二叉树的深度是一道简单题,题目如下:
输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。
由于二叉树有多种分支,在遍历前,我们并不知道哪条路线是最深的,所以必须利用递归尝试。
我们可以转换一下思路,用函数式语义方式来理解。假设我们有了这样一个函数 deep 来求二叉树深度,那么这个函数内容是什么呢?二叉树只可能存在左右子树,所以 deep 必然是左右子树的最大深度的最大值 +1(它自己)。
而求左右子树深度可以复用 deep 函数形成递归,我们只需要考虑边界情况,即访问节点不存在时,返回深度 0 即可,因此代码如下:
function deep(node: TreeNode) {
if (!node) return 0
return Math.max(deep(node.left), deep(node.right)) + 1
}
从这可以看出,二叉树一般能用比较优雅的递归函数解决,如果你的解题思路不包含递归,往往就不是最优雅的解法。
类似优雅的题目还有,平衡二叉树。
声明:本文内容由网友自发贡献,本站不承担相应法律责任。对本内容有异议或投诉,请联系2913721942#qq.com核实处理,我们将尽快回复您,谢谢合作!
若转载请注明出处: 算法 - 二叉树
本文地址: https://pptw.com/jishu/658339.html