1. 统一风格迭代法原理

1.1 问题描述

前序和后序本质一样：根左右 -> 根右左 -> 左右根

只需改变前序遍历的左右子树处理顺序，再reverse最终结果，即得后序遍历

但是难以统一前序后序与中序

核心问题：节点访问顺序与处理顺序不同！

以中序遍历为例，先访问根节点，但此时不能处理（输出结果），必须等左子树处理完毕，才能处理根节点。

1.2 解决思路

preorder 根左右进栈顺序应为右左根

inorder 左根右进栈顺序应为右根左

postorder 左右根进栈顺序应为根右左

将访问的节点放入栈中，把要处理的节点也放入栈中但是要紧接着放入一个空指针作为标记。

只有当遇到空指针时，才将栈顶下一个节点放进结果集

1.3 前序遍历代码

public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> result = new LinkedList<>();
       Stack<TreeNode> st = new Stack<>();
       if (root != null) st.push(root);
       while (!st.empty()) {
           TreeNode node = st.peek();
           if (node != null) {
               st.pop(); // 将该节点弹出，避免重复操作，下面再将右左根节点添加到栈中
               if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
               if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
               st.push(node);                          // 添加中节点
               st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
               
           } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
               st.pop();           // 将空节点弹出
               node = st.peek();    // 重新取出栈中元素
               st.pop();
               result.add(node.val); // 加入到结果集
           }
       }
       return result;
   }

1.4 中序遍历代码

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
    Stack<TreeNode> st = new Stack<>();
    if (root != null) st.push(root);
    while (!st.empty()) {
        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();
            result.add(node.val); // 加入到结果集
        }
    }
    return result;
}

1.5 后序遍历代码

public List<Integer> postorderTraversal(TreeNode root) {
       List<Integer> result = new LinkedList<>();
       Stack<TreeNode> st = new Stack<>();
       if (root != null) st.push(root);
       while (!st.empty()) {
           TreeNode node = st.peek();
           if (node != null) {
               st.pop(); // 将该节点弹出，避免重复操作，下面再将根右左节点添加到栈中
               st.push(node);                          // 添加中节点
               st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
               if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
               if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         
                              
           } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
               st.pop();           // 将空节点弹出
               node = st.peek();    // 重新取出栈中元素
               st.pop();
               result.add(node.val); // 加入到结果集
           }
       }
       return result;
  }

IVN

二叉树的统一风格迭代法