知识文档站

Appearance

二叉树遍历非递归实现

先序遍历 ​

题目链接 ​

https://leetcode.cn/problems/binary-tree-preorder-traversal/ ​

思路分析 ​

中序遍历的顺序是：中、左、右 ​

利用栈的特点，后进先出，则进栈顺序为：先压入根节点，弹出根节点，同时将左右子树节点进栈，先压入右子树，再压入左子树 ​

代码实现 ​

java
class Solution {
    public List<Integer> preorderTraversal(TreeNode head) {
        List<Integer> ans = new ArrayList<>();
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            // 将根节点入栈
            stack.push(head);
            while (!stack.isEmpty()) {
                // 根节点弹出，将左右子树根节点入栈
                // 根据栈的特点，先压入右子树节点，后压入左子树节点
                head = stack.pop();
                ans.add(head.val);
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        return ans;
    }
}

中序遍历 ​

题目链接 ​

https://leetcode.cn/problems/binary-tree-inorder-traversal/ ​

思路分析 ​

（1）先处理左子树，递归遍历到头，将节点入栈 ​

（2）若左子树为空，弹出栈顶元素，处理右子树（指针来到右子树） ​

（3）右子树的处理方式又是延续（1）的方法，先处理左子树...... ​

代码实现 ​

java
class Solution {
    public List<Integer> inorderTraversal(TreeNode head) {
        List<Integer> ans = new ArrayList<>();
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            // 栈不为空 || 子树不为空
            while (!stack.isEmpty() || head != null) {
                // 只要左树不为空，一路把左树入栈
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    // 左树为空，弹出根节点，处理右子树
                    head = stack.pop();
                    ans.add(head.val);
                    head = head.right;
                }
            }
        }
        return ans;
    }
}

后序遍历 ​

题目链接 ​

https://leetcode.cn/problems/binary-tree-postorder-traversal/ ​

思路分析 ​

（1）两个栈实现 ​

先序遍历顺序：中、左、右 ​

后序遍历顺序：左、右、中 ​

根据栈的特点，后进先出，先压左，再压右，节点顺序：中、右、左 ​

将该节点顺序反转后即为后序遍历顺序，这里可以借助一个栈来实现，将弹出的元素放到新的栈中 ​

遍历完成后，把新栈中的元素全部依次弹出，即可得到后序遍历顺序 ​

（2）一个栈实现 ​

先将根节点入栈 ​

先处理左树，再处理右树，左树、右树 没有 或者 都处理过了，打印栈顶元素，head 来到该元素的位置 ​

在下一轮遍历中，head 表示上一轮打印的节点，也可以理解为 head 指针充当哨兵的作用，用来标记左右子树是否处理过 ​

两个栈实现 ​

java
class Solution {
    public List<Integer> postorderTraversal(TreeNode head) {
        List<Integer> ans = new ArrayList<>();
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> collect = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                // 将出栈节点压入新栈，出栈顺序，中、右、左 --> 左、右、中
                collect.push(head);
                // 先压左，再压右，出栈顺序--> 中、右、左
                if (head.left != null) {
                    stack.push(head.left);
                }
                if (head.right != null) {
                    stack.push(head.right);
                }
            }
            while (!collect.isEmpty()) {
                ans.add(collect.pop().val);
            }
        }
        return ans;
    }
}

一个栈实现（推荐） ​

java
class Solution {
    public List<Integer> postorderTraversal(TreeNode head) {
        List<Integer> ans = new ArrayList<>();
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);
            // 如果始终没有打印过节点，head 就一直是头节点
            // 一旦打印过节点，head 就变成打印节点
            // 之后 head 的含义 : 上一次打印的节点
            while (!stack.isEmpty()) {
                TreeNode cur = stack.peek();
                if (cur.left != null && head != cur.left && head != cur.right) {
                    // 有左树且左树没处理过
                    stack.push(cur.left);
                } else if (cur.right != null && head != cur.right) {
                    // 有右树且右树没处理过
                    stack.push(cur.right);
                } else {
                    // 左树、右树 没有 或者 都处理过了
                    ans.add(cur.val);
                    head = stack.pop();
                }
            }
        }
        return ans;
    }
}

本节测试代码 ​

java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// 不用递归，用迭代的方式实现二叉树的三序遍历
public class BinaryTreeTraversalIteration {

	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int v) {
			val = v;
		}
	}

	// 先序打印所有节点，非递归版
	public static void preOrder(TreeNode head) {
		if (head != null) {
			Stack<TreeNode> stack = new Stack<>();
			stack.push(head);
			while (!stack.isEmpty()) {
				head = stack.pop();
				System.out.print(head.val + " ");
				if (head.right != null) {
					stack.push(head.right);
				}
				if (head.left != null) {
					stack.push(head.left);
				}
			}
			System.out.println();
		}
	}

	// 中序打印所有节点，非递归版
	public static void inOrder(TreeNode head) {
		if (head != null) {
			Stack<TreeNode> stack = new Stack<>();
			while (!stack.isEmpty() || head != null) {
				if (head != null) {
					stack.push(head);
					head = head.left;
				} else {
					head = stack.pop();
					System.out.print(head.val + " ");
					head = head.right;
				}
			}
			System.out.println();
		}
	}

	// 后序打印所有节点，非递归版
	// 这是用两个栈的方法
	public static void posOrderTwoStacks(TreeNode head) {
		if (head != null) {
			Stack<TreeNode> stack = new Stack<>();
			Stack<TreeNode> collect = new Stack<>();
			stack.push(head);
			while (!stack.isEmpty()) {
				head = stack.pop();
				collect.push(head);
				if (head.left != null) {
					stack.push(head.left);
				}
				if (head.right != null) {
					stack.push(head.right);
				}
			}
			while (!collect.isEmpty()) {
				System.out.print(collect.pop().val + " ");
			}
			System.out.println();
		}
	}

	// 后序打印所有节点，非递归版
	// 这是用一个栈的方法
	public static void posOrderOneStack(TreeNode h) {
		if (h != null) {
			Stack<TreeNode> stack = new Stack<>();
			stack.push(h);
			// 如果始终没有打印过节点，h就一直是头节点
			// 一旦打印过节点，h就变成打印节点
			// 之后h的含义 : 上一次打印的节点
			while (!stack.isEmpty()) {
				TreeNode cur = stack.peek();
				if (cur.left != null && h != cur.left && h != cur.right) {
					// 有左树且左树没处理过
					stack.push(cur.left);
				} else if (cur.right != null && h != cur.right) {
					// 有右树且右树没处理过
					stack.push(cur.right);
				} else {
					// 左树、右树 没有 或者 都处理过了
					System.out.print(cur.val + " ");
					h = stack.pop();
				}
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		TreeNode head = new TreeNode(1);
		head.left = new TreeNode(2);
		head.right = new TreeNode(3);
		head.left.left = new TreeNode(4);
		head.left.right = new TreeNode(5);
		head.right.left = new TreeNode(6);
		head.right.right = new TreeNode(7);
		preOrder(head);
		System.out.println("先序遍历非递归版");
		inOrder(head);
		System.out.println("中序遍历非递归版");
		posOrderTwoStacks(head);
		System.out.println("后序遍历非递归版 - 2个栈实现");
		posOrderOneStack(head);
		System.out.println("后序遍历非递归版 - 1个栈实现");
	}
}

Copyright © 2025 Jackson 凌 All Rights Reserved. | 粤ICP备2025441629号-1