面试手撕——迭代法中序遍历二叉树

思路

访问顺序和处理顺序不一致导致迭代法难写，体现在总要先遍历根节点，才能访问左右孩子，用null标记，null标记的节点表示已经访问过了，下一次可以处理，所以在当前栈顶节点不是null的时候，都要进行入栈，由于是左根右的处理顺序，所以压栈的时候要右根左压栈。

代码

import java.util.Stack;public class InOrderTraversalBinaryTree {static class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(int v){this.val = v;this.left = null;this.right = null;}}static void InOrderTra(TreeNode root){if(root == null) return;if(root.left != null) InOrderTra(root.left);System.out.println(root.val);if(root.right != null) InOrderTra(root.right);}public static void main(String[] args) {TreeNode root = new TreeNode(7);TreeNode left = new TreeNode(3);TreeNode right = new TreeNode(10);root.left = left;root.right = right;
//      递归法
//        InOrderTra(root);Stack<TreeNode> st = new Stack<>();if(root != null)st.push(root);while(!st.isEmpty()){TreeNode node = st.peek();if(node != null){st.pop();if(node.right != null) st.push(node.right);st.push(node);st.push(null);if(node.left != null) st.push(node.left);}else{st.pop();node = st.peek();st.pop();System.out.println(node.val);}}}}