原题链接:
三道题的解决思路可统一,模板也极其相似,比九章提供的更漂亮。
比如{1,2,3},当cur位于节点1时,1、2属于“左”节点,3属于“右”节点。DFS的非递归实现本质上是在协调入栈、出栈和访问,三种操作的顺序。上述统一使得我们不再需要关注入栈顺序,仅需要关注出栈和访问(第3点),随着更详细的分析,你将更加体会到这种简化带来的好处。
将对节点的访问定义为
,分析如下:
- results.add(node.val);
先序和中序的情况是极其相似的。
使用上述思路,先序和中序的遍历顺序可统一为:“左”“右”。
给我们的直观感觉是代码也会比较相似。实际情况正是如此,先序与中序的区别只在于对“左”节点的访问上。
不需要入栈,每次遍历到“左”节点,立即输出即可。
需要注意的是,遍历到最左下的节点时,实际上输出的已经不再是实际的根节点,而是实际的左节点。这符合先序的定义。
- while (cur != null) {
- results.add(cur.val);
- stack.push(cur);
- cur = cur.left;
- }
而后,因为我们已经访问过所有“左”节点,现在只需要将这些没用的节点出栈,然后转向到“右”节点。于是“右”节点也变成了“左”节点,后续处理同上。
- if (!stack.empty()) {
- cur = stack.pop();
- // 转向
- cur = cur.right;
- }
完整代码如下:
- private List < Integer > dfsPreOrder(TreeNode root) {
- List < Integer > results = new ArrayList < >();
- Stack < TreeNode > stack = new Stack < >();
- TreeNode cur = root;
- while (cur != null || !stack.empty()) {
- while (cur != null) {
- results.add(cur.val);
- stack.push(cur);
- cur = cur.left;
- }
- if (!stack.empty()) {
- cur = stack.pop();
- // 转向
- cur = cur.right;
- }
- }
- return results;
- }
基于对先序的分析,
,我们调整一行代码即可完成中序遍历。
- 先序与中序的区别只在于对“左”节点的处理上
- while (cur != null) {
- stack.push(cur);
- cur = cur.left;
- }
- if (!stack.empty()) {
- cur = stack.pop();
- results.add(cur.val); // 仅调整该行代码
- // 转向
- cur = cur.right;
- }
注意,我们在出栈之后才访问这个节点。因为先序先访问实际根,后访问实际左,而中序恰好相反。相同的是,访问完根+左子树(先序)或左子树+根(中序)后,都需要转向到“右”节点,使“右”节点称为新的“左”节点。
完整代码如下:
- private List < Integer > dfsInOrder(TreeNode root) {
- List < Integer > results = new ArrayList < >();
- Stack < TreeNode > stack = new Stack < TreeNode > ();
- TreeNode cur = root;
- while (cur != null || !stack.empty()) {
- while (cur != null) {
- stack.push(cur);
- cur = cur.left;
- }
- if (!stack.empty()) {
- cur = stack.pop();
- results.add(cur.val);
- // 转向
- cur = cur.right;
- }
- }
- return results;
- }
后序的情况略有不同,但仍然十分简洁。
入栈顺序不变,我们只需要考虑第3点的变化。出栈的对象一定都是“左”节点(“右”节点会在转向后称为“左”节点,然后入栈),也就是实际的左或根;实际的左可以当做左右子树都为null的根,所以我们只需要分析实际的根。
对于实际的根,需要保证先后访问了左子树、右子树之后,才能访问根。实际的右节点、左节点、根节点都会成为“左”节点入栈,所以我们只需要在出栈之前,将该节点视作实际的根节点,并检查其右子树是否已被访问即可。如果不存在右子树,或右子树已被访问了,那么可以访问根节点,出栈,并不需要转向;如果还没有访问,就转向,使其“右”节点成为“左”节点,等着它先被访问之后,再来访问根节点。
所以,我们需要增加一个标志,记录右子树的访问情况。由于访问根节点前,一定先紧挨着访问了其右子树,所以我们只需要一个标志位。
完整代码如下:
- private List < Integer > dfsPostOrder(TreeNode root) {
- List < Integer > results = new ArrayList < >();
- Stack < TreeNode > stack = new Stack < >();
- TreeNode cur = root;
- TreeNode last = null;
- while (cur != null || !stack.empty()) {
- while (cur != null) {
- stack.push(cur);
- cur = cur.left;
- }
- if (!stack.empty()) {
- cur = stack.peek();
- // 如果已经访问了右子树,则可以访问根节点;否则转向,先去访问右子树
- if (cur.right == null || cur.right == last) {
- results.add(cur.val);
- stack.pop();
- last = cur; // 表示已访问过
- cur = null; // 表示不需要转向,继续弹栈
- } else {
- // 转向
- cur = cur.right;
- }
- }
- }
- return results;
- }
思路简洁万岁!模板大法万岁!
消灭人类暴政,世界属于三体!
来源: https://juejin.im/post/59e3fde451882578c20858a5