【JAVA】二叉树迭代遍历的统一写法（代码注释详解）

 
    private List iterateTemplate(TreeNode root) {
        Deque stack = new ArrayDeque<>();
        List resultList = new ArrayList<>();
        TreeNode curNode = root; // 当前节点
        while (!stack.isEmpty() || curNode != null) {
            if (curNode != null) {
               // 左节点入栈过程
            } else {
                // 从栈中取
            }
        }
        return resultList;
    }

    
    private List preOrderIterate(TreeNode root) {
        Deque stack = new ArrayDeque<>();
        List resultList = new ArrayList<>();
        TreeNode curNode = root;
        while (!stack.isEmpty() || curNode != null) {
            if (curNode != null) {
                stack.push(curNode);
                resultList.add(curNode.val);
                curNode = curNode.left;
            } else {
                // 从栈中取
                curNode = stack.pop();
                curNode = curNode.right;
            }
        }
        return resultList;
    }

    
    private List inorderIterate(TreeNode root) {
        Deque stack = new ArrayDeque<>();
        List resultList = new ArrayList<>();
        TreeNode curNode = root;
        while (!stack.isEmpty() || curNode != null) {
            if (curNode != null) {
                //【1】
                stack.push(curNode);
                curNode = curNode.left;
            } else {
                // 节点为空，进行出栈【2】
                curNode = stack.pop();
                resultList.add(curNode.val);
                if (curNode.right != null) {
                    //【3】
                    curNode = curNode.right;
                } else {
                    // 没有右节点时要置空，下一个元素从栈内拿
                    curNode = null;
                }
            }
        }
        return resultList;
    }

    
    private List postOrderIterate(TreeNode root) {
        List result = new ArrayList<>();
        Deque stack = new ArrayDeque<>();
        TreeNode curNode = root; // 标志当前节点（当节点进行入栈时不为空，节点为空时标志该出栈）
        TreeNode lastPopNode = null;// 记录上一个出栈的node
        while (!stack.isEmpty() || curNode != null) {
            if (curNode != null) {
                // 延左子树向下寻找【1】
                stack.push(curNode);
                curNode = curNode.left;
            } else {
                // curNode == null 表示左子树遍历到头/正在出栈
                curNode = stack.peek(); // 先不弹出，可能是第一次访问
                if (curNode.right == null || curNode.right == lastPopNode) {
                    // 没有右子树/右子树已访问过【3】
                    stack.pop(); // 可以弹出
                    lastPopNode = curNode;
                    result.add(curNode.val);
                    curNode = null; // 注意要把curNode置空
                } else {
                    // 有右子树且右子树未被访问过【2】
                    curNode = curNode.right; // 进入右子树
                }
            }
        }
        return result;
    }

TreeNode节点定义如下：

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

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

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

最重要的还是自己实践之后形成自己的经验