题解 | #实现二叉树先序，中序和后序遍历#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        // write code here
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        List<Integer> list3 = new ArrayList<>();
        
        //先序
        PreOrder(root,list1);
        //中序
        InOrder(root,list2);
        //后序
        PostOrder(root,list3);
        int[][] arr = new int[3][list1.size()];
        for(int i=0;i<list1.size();i++){
            arr[0][i] = list1.get(i);
             arr[1][i] = list2.get(i);
             arr[2][i] = list3.get(i);
        }
        return arr;
    }
    public void PreOrder(TreeNode node,List<Integer> list){
         if(node!=null){
            list.add(node.val);
            PreOrder(node.left,list);
            PreOrder(node.right,list);
        }
        
    }
    public void InOrder(TreeNode node,List<Integer> list){
         if(node!=null){
            InOrder(node.left,list);
            list.add(node.val);
            InOrder(node.right,list);
        }
       
    }
    //递归
//     public void PostOrder(TreeNode node,List<Integer> list){
        
//          if(node!=null){
//             PostOrder(node.left,list);
//             PostOrder(node.right,list);
//             list.add(node.val);
//         }
//     }
    //后序使用迭代实现
    public void PostOrder(TreeNode node,List<Integer> list){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode r = null;
        while(node!=null||!stack.isEmpty()){
            if(node!=null){
                stack.push(node);
                node = node.left;   
            }else{
                node = stack.peek();
                 if(node.right!=null && node.right!=r){//右子树存在且未被访问
                    node = node.right;  
                }else{
                    list.add(node.val);
                    stack.pop();
                    r = node;
                    node = null;
                 }
            }
        }
    }
       
}

总结： 1.二叉树遍历分为递归和迭代两种方法。 递归写起来相对简单，但不适合递归深度太深的情况。
二者的关系：递归本质是隐性维护一个栈，而迭代是显示的将该栈模拟出来。
2.迭代写法的后序遍历较为复杂。必须分清返回时是从左子树返回的还是右子树返回的，因此设置了一个辅助指针r，指向最近访问过的节点。