如题,在今天刷题时碰到了这样一道二叉树的题目,原题地址在这里:
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal?envType=study-plan-v2&envId=top-interview-150
在官方题解中已经给出了使用递归的解法,讲解还是比较清晰的,但是我在理解迭代做法的时候却觉得很难理解,在这里详细拆解一下步骤并给出C#源代码。
给出本次分析要用的示例二叉树:
3/ \9 20/ \ \15 10 7/ \5 8\4
保证树的每个节点的值不重复。
它的中序遍历和后序遍历分别为
inorder = [15, 9, 10, 3, 20, 5, 7, 8, 4]
postorder = [15, 10, 9, 5, 4, 8, 7, 20, 3]
先说结论:我们使用一个指针index(初始指向中序的最后一个位置)和一个栈(维护二叉树的层次结构,栈顶为当前正在分析的节点)辅助构建这个二叉树。我们将后序遍历的最后一个节点入栈,然后从倒数第二个开始,往前依次检查每一个节点。
对于栈顶节点:
*如果栈顶节点和index指向的节点不一致,代表正在检查的节点不可能是栈顶节点的左儿子,于是将这个节点作为栈顶节点的右儿子入栈。
*如果栈顶节点和index指向的节点一致,代表正在检查的节点不可能是栈顶节点的右儿子,但不一定是左儿子,而可能是栈顶节点某个祖先节点的左子树中的某个神必节点,所以需要找到是哪个祖先节点的左子树,于是将栈顶节点弹出,并将index左移一位,检查index指向的节点是不是正在检查的那个节点,如果是,那么刚刚弹出的那个节点就是该节点的父节点,所以将该节点作为刚刚弹出的那个节点的左儿子入栈。如果不是则重复刚刚的操作,继续弹出栈顶节点并左移index。如果直到栈空都还没找到对应的index,那就代表这个节点不可能在栈顶节点的右边,而只能是左子树的一点,而且只可能是栈顶节点的左儿子,于是将其作为刚刚弹出的那个栈顶节点的左儿子入栈。
*如果将后序遍历的最后一个节点入栈,算法就结束了,我们已经构建完成。
以上两个原则(除了最后一个结束条件算凑数的)是怎么来的呢?
首先看中序遍历和后序遍历的特点:
中序遍历:按照“左子树->根节点->右子树”的顺序遍历,也就是说对于遍历列表中的某个节点,左边的全是左子树的节点,右边全是右子树的节点。如果我们把这个列表倒过来(至于为什么要倒过来,等会看看后序遍历的特点就知道了),那就是按照“右子树->根节点->左子树”的顺序遍历,已经遍历过的节点一定在现在正在检查的这个节点的右子树中。
后序遍历:按照“左子树->右子树->根节点”的顺序遍历,如果把遍历列表倒过来,第一个就是整棵树的根节点,然后按顺序可以找到根节点的右子树,最后是左子树。
那么我们可以开始工作了,用栈保存节点,是为了从根节点开始向下分析,先找右子树。右子树找完,可能会有几个节点有左子树,那么我们可以将没有左子树的节点弹出,找到有左子树的那个层次去构建左子树,然后继续从这个左子树开始往它的右子树走,重复以上分析,最后完成整棵树的构建。采用这个顺序,是因为后序遍历倒过来就如刚刚所说,是按照根节点-右子树-左子树来走的。
第一个入栈的节点是根节点3,然后我们检查3的下一个节点(也就是20),因为当前index指向的是inorder的最后一个,也就是4,根据原则一,我们认为20是3的右儿子。这是因为根据中序遍历的特点,如果3没有右子树,那么3应该是中序遍历的最后一个节点,那inorder的最后一个节点应该是3才对,所以这不可能,20一定是3的右儿子,入栈吧。
同理20也不会是最右边的节点,不然中序遍历的最后一个应该是20,所以20的右子树肯定还有东西,7作为20的右儿子入栈。
7和8也同理,就不用说了。轮到检查5,此时栈顶节点是4……
这里插个题外话,我写到这里的时候有点懵,因为不知道4这个节点是不是需要特殊情况讨论,后来想半天才反应过来,我们检查的节点是栈顶节点的下一个,我们对比和index指向的节点是不是一样的那个节点,是栈顶节点而不是检查中的节点(所以我这个“检查”的措辞用得是真垃圾,但是这个文章没有方便的F2重命名,就算了8 XD)
回到正题,检查节点5,此时栈顶为4,终于检查到了一个和index指向节点一样的栈顶节点,这意味着什么呢,由于中序遍历按照“左中右”的顺序遍历,最右边的节点不可能还有右子树了,所以4不可能还有右子树,所以我们检查的这个5要么是4的左子树中的某一点,要么是4的某个祖先节点的左子树中的某一点,现在我们可以开始找是哪个祖宗了。
现在栈里面从底部开始按顺序为3-20-7-8-4,只要按顺序弹出,我们就可以从3的右子树的底部往上一层一层找5是谁的左儿子……(顺带一提为什么一定是左儿子呢,有点长加一段吧)
如果这个5在节点3和节点4中间某一层:它一定是栈里面某个节点的左儿子,因为按照后序遍历,5所在层级的遍历顺序是这样的:左子树->右子树->节点5->父节点的右子树->父节点,所以我们刚刚已经找完4后面的节点了,所以一定会先找到5才会找到5的右子树,然后是5的左子树,所以我们才可以断定5一定是某个节点的左儿子。
我们在一层一层弹栈的时候(还记得吗,每次index左移一位并将栈顶节点弹出,意味着我们从树右边底部开始往前面回溯了)就会排除完右子树的节点,在弹出父节点的时候会发现index指向的新节点和栈顶节点不一样诶,这意味着index指针在反向的中序遍历过程中,右边子树都已经逛完了,刚找到了5的父节点(7),现在来到5这个节点了,所以我们可以断定5就是7的左儿子,将其作为7的左儿子入栈。那么5就会作为一个全新的子树根节点,开始重复之前的操作,从右子树开始检查……到这一步是不是有点递归那种思想的感觉了?如果是的话那离算法完成已经不远了。
现在我们讨论最后一种情况(实际上和上一点是同样的情况)也就是栈空,这意味着我们要找的节点一定是刚弹出的那个节点的左儿子,毕竟栈都弹空了,栈顶节点的右子树肯定已经找完了,那只能是刚弹出的那个栈顶节点的左儿子咯。
以下是C#源代码(顺带一提我是从写完写到这里才开始写代码,因为真的太tm难懂了,好不容易整理这一大堆废话才明白自己在说什么各位读者不要介意):
public TreeNode BuildTree(int[] inorder, int[] postorder){int index = inorder.Length - 1;Stack<TreeNode> stack = [];TreeNode top, current, result = new(postorder[^1]);//先将后序遍历的最后一个元素作为根节点入栈,从倒数第二个元素开始检查stack.Push(result);for (int i = postorder.Length - 2; i >= 0; i--){top = stack.Peek();current = new(postorder[i]);//如果栈顶节点和index指向的节点不一致,//代表正在检查的节点不可能是栈顶节点的左儿子,//将这个节点作为栈顶节点的右儿子入栈if (top.val != inorder[index]){top.right = current;stack.Push(current);}//如果栈顶节点和index指向的节点一致,则开始找祖宗环节else{while (stack.Count > 0 && stack.Peek().val == inorder[index]){top = stack.Pop();index--;}//找到了祖先节点,将这个节点作为栈顶节点的左儿子入栈top.left = current;stack.Push(current);}}return result;}