当前位置：首页 > ds >正文

二叉树迭代遍历——给一个属性便可实现迭代结构完美统一

ds 2025/8/26 3:57:36

回顾二叉树的递归遍历

树结点

class TreeNode {TreeNode left;TreeNode right;int val;public TreeNode(TreeNode left, TreeNode right, int val) {this.left = left;this.right = right;this.val = val;}
}

前序递归遍历

public void preOrderRecur(Node head){if (head==null){return;}System.out.print(head.value+" ");preOrderRecur(head.left);preOrderRecur(head.right);
}

中序递归遍历

public void inOrderRecur(Node head){if (head==null){return;}inOrderRecur(head.left);System.out.print(head.value+" ");inOrderRecur(head.right);
}

后序递归遍历

public void postOrderRecur(Node head){if(head==null){return;}postOrderRecur(head.left);postOrderRecur(head.right);System.out.print(head.value+" ");
}

分析与思路

目标与期待

$\odot:$ 递归遍历非常方便，仅需移动输出head.value的顺序变可实现三种遍历，这是因为树的定义本来就是遵循递归所导致。因此，我们自然也想，树的非递归（迭代）遍历如果是这样就好了。

难点

$\odot:$ 首先自然得用到栈来模拟递归中涉及的变量栈。在非递归的条件下，前序遍历还是比较容易实现，只需打印head.value之后立马在栈中先后push进head.right和head.left即可（由于栈先进后出，因此我们后push进head.left，以便下一次先拿到是head.left）。

$\odot:$ 然而，但对中序遍历来说就特别麻烦，对于拿到的head，我们得先遍历完head的左子树才能输出head.value，之后才能push进head.right。换句话来说**，push进head.right和head.left应该是分开的，不能连在一起**，因此我们也得分两次拿到head以便分别push进head.right和head.left。

思路

$\odot:$ 因此，最关键的问题来了，拿到head之后，到底哪次该push进head.right，到底哪次该push进head.left。可以看到市面上很多的代码，各种额外的操作，其实本质就是在解决这个问题。

$\odot:$ 而我的想法就很简单，直接给树结点额外加个属性flag，记录其是第一次拿到head，还是第二次。添加属性flag之后，整个二叉树的迭代得到完美的统一。

代码实现

额外添加一个属性，但不改变原来TreeNode的结构。比如leetcode是无法改变提供好的TreeNode结构的，但我们可以自定义新的class。

class TreeNodeWithFlag {TreeNode treeNode;//flag为true，表明该节点可以直接输出，一开始为falseboolean flag;public TreeNodeWithFlag(TreeNode treeNode, boolean flag) {this.treeNode = treeNode;this.flag = flag;}
}

前序迭代遍历

    public static List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNodeWithFlag> st = new Stack<>();if (root != null) st.push(new TreeNodeWithFlag(root, false));while (!st.empty()) {TreeNodeWithFlag node = st.pop();if (!node.flag) {//flag为false，下面再将右中左节点添加到栈中// 添加右节点（空节点不入栈）if (node.treeNode.right != null) st.push(new TreeNodeWithFlag(node.treeNode.right, false));// 添加左节点（空节点不入栈）if (node.treeNode.left != null) st.push(new TreeNodeWithFlag(node.treeNode.left, false));//左右孩子已经处理过，令flag为true，表明下次访问到可以直接输出//对于前序遍历可以，其实下次循环必定就是输出node了node.flag=true;// 添加中节点st.push(node);//最终进栈时，保持右左中的顺序，出栈时保持中左右的顺序} else {//flag为true，表明该节点可以直接输出result.add(node.treeNode.val); // 加入到结果集}}return result;}

中序迭代遍历

    public static List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNodeWithFlag> st = new Stack<>();if (root != null) st.push(new TreeNodeWithFlag(root, false));while (!st.empty()) {TreeNodeWithFlag node = st.pop();if (!node.flag) {//flag为false，下面再将右中左节点添加到栈中// 添加右节点（空节点不入栈）if (node.treeNode.right != null) st.push(new TreeNodeWithFlag(node.treeNode.right, false));//右孩子已经处理过，令flag为true，表明下次访问到可以直接输出node.flag=true;// 添加中节点st.push(node);// 添加左节点（空节点不入栈）if (node.treeNode.left != null) st.push(new TreeNodeWithFlag(node.treeNode.left, false));//最终进栈时，保持右中左的顺序，出栈时保持左中右的顺序} else {//flag为true，表明该节点可以直接输出result.add(node.treeNode.val); // 加入到结果集}}return result;}

后序迭代遍历

    public static List<Integer> postOrderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNodeWithFlag> st = new Stack<>();if (root != null) st.push(new TreeNodeWithFlag(root, false));while (!st.empty()) {TreeNodeWithFlag node = st.pop();if (!node.flag) {//flag为false，下面再将中右左节点添加到栈中//令flag为true，表明下次访问到可以直接输出，再处理左右孩子node.flag=true;// 先添加中节点st.push(node);// 添加右节点（空节点不入栈）if (node.treeNode.right != null) st.push(new TreeNodeWithFlag(node.treeNode.right, false));// 添加左节点（空节点不入栈）if (node.treeNode.left != null) st.push(new TreeNodeWithFlag(node.treeNode.left, false));//最终进栈时，保持中右左的顺序，出栈时保持左右中的顺序} else {//flag为true，表明该节点可以直接输出result.add(node.treeNode.val); // 加入到结果集}}return result;}

具体例子

树的逻辑结构：

    public static void main(String[] args) {TreeNode treeNode1 = new TreeNode(null, null, 1);TreeNode treeNode2 = new TreeNode(null, null, 2);TreeNode treeNode3 = new TreeNode(null, null, 3);TreeNode treeNode4 = new TreeNode(null, null, 4);TreeNode treeNode5 = new TreeNode(null, null, 5);TreeNode treeNode6 = new TreeNode(treeNode1, null, 6);TreeNode treeNode7 = new TreeNode(treeNode3, treeNode2, 7);TreeNode treeNode8 = new TreeNode(treeNode5, treeNode4, 8);TreeNode treeNode9 = new TreeNode(treeNode7, treeNode6, 9);TreeNode treeNode10 = new TreeNode(treeNode9, treeNode8, 10);System.out.print("前序遍历:");preorderTraversal(treeNode10).forEach(System.out::print);System.out.print("\n中序遍历:");inorderTraversal(treeNode10).forEach(System.out::print);System.out.print("\n后序遍历:");postOrderTraversal(treeNode10).forEach(System.out::print);}