C++如何实现二叉树的后序遍历


本篇内容主要讲解“C++如何实现二叉树的后序遍历”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“C++如何实现二叉树的后序遍历”吧!Given a binary tree, return 香港云主机 thepostordertraversal of its nodes” values.For example:
Given binary tree {1,#,2,3}, 1

2
/
3return [3,2,1].Note:Recursive solution is trivial, could you do it iteratively?经典题目,求二叉树的后序遍历的非递归方法,跟前序,中序,层序一样都需要用到栈,后序的顺序是左-右-根,所以当一个结点值被取出来时,它的左右子结点要么不存在,要么已经被访问过了。先将根结点压入栈,然后定义一个辅助结点 head,while 循环的条件是栈不为空,在循环中,首先将栈顶结点t取出来,如果栈顶结点没有左右子结点,或者其左子结点是 head,或者其右子结点是 head 的情况下。将栈顶结点值加入结果 res 中,并将栈顶元素移出栈,然后将 head 指向栈顶元素;否则的话就看如果右子结点不为空,将其加入栈,再看左子结点不为空的话,就加入栈,注意这里先右后左的顺序是因为栈的后入先出的特点,可以使得左子结点先被处理。下面来看为什么是这三个条件呢,首先如果栈顶元素如果没有左右子结点的话,说明其是叶结点,而且入栈顺序保证了左子结点先被处理,所以此时的结点值就可以直接加入结果 res 了,然后移出栈,将 head 指向这个叶结点,这样的话 head 每次就是指向前一个处理过并且加入结果 res 的结点,那么如果栈顶结点的左子结点或者右子结点是 head 的话,说明其子结点已经加入结果 res 了,那么就可以处理当前结点了。看到这里,大家可能对 head 的作用,以及为何要初始化为 root,还不是很清楚,这里再解释一下。head 是指向上一个被遍历完成的结点,由于后序遍历的顺序是左-右-根,所以一定会一直将结点压入栈,一直到把最左子结点(或是最左子结点的最右子结点)压入栈后,开始进行处理。一旦开始处理了,head 就会被重新赋值。所以 head 初始化值并没有太大的影响,唯一要注意的是不能初始化为空,因为在判断是否打印出当前结点时除了判断是否是叶结点,还要看 head 是否指向其左右子结点,如果 head 指向左子结点,那么右子结点一定为空,因为入栈顺序是根-右-左,不存在右子结点还没处理,就直接去处理根结点了的情况。若 head 指向右子结点,则是正常的左-右-根的处理顺序。那么回过头来在看,若 head 初始化为空,且此时正好左子结点不存在,那么在压入根结点时,head 和左子结点相等就成立了,此时就直接打印根结点了,明显是错的。所以 head 只要不初始化为空,一切都好说,甚至可以新建一个结点也没问题。将 head 初始化为 root,也可以,就算只有一个 root 结点,那么在判定叶结点时就将 root 打印了,然后就跳出 while 循环了,也不会出错。代码如下:解法一:由于后序遍历的顺序是左-右-根,而先序遍历的顺序是根-左-右,二者其实还是很相近的,可以先在先序遍历的方法上做些小改动,使其遍历顺序变为根-右-左,然后翻转一下,就是左-右-根啦,翻转的方法我们使用反向Q,哦不,是反向加入结果 res,每次都在结果 res 的开头加入结点值,而改变先序遍历的顺序就只要该遍历一下入栈顺序,先左后右,这样出栈处理的时候就是先右后左啦,参见代码如下:解法二:那么在Binary Tree Preorder Traversal中的解法二也可以改动一下变成后序遍历,改动的思路跟上面的解法一样,都是先将先序遍历的根-左-右顺序变为根-右-左,再翻转变为后序遍历的左-右-根,翻转还是改变结果 res 的加入顺序,然后把更新辅助结点p的左右顺序换一下即可,代码如下:解法三:论坛上还有一种双栈的解法,其实本质上跟解法二没什么区别,都是利用了改变先序遍历的顺序来实现后序遍历的,参见代码如下:解法四:到此,相信大家对“C++如何实现二叉树的后序遍历”有了更深的了解,不妨来实际操作一番吧!这里是开发云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

相关推荐: Windows中怎么设置本地组策略编辑器禁止访问控制面板

这篇文章主要为大家展示了“Windows中怎么设置本地组策略编辑器 香港云主机禁止访问控制面板”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“Windows中怎么设置本地组策略编辑器禁止访问控制面板”这篇文章吧。1、…

免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 07/14 16:29
下一篇 07/14 16:29

相关推荐