二叉树的前中后序遍历的两种方法

前中后序遍历的记忆方式:前中后可以记为中间节点的顺序位置，如:前序遍历:中左右;中序遍历:左中右;后续遍历:左右中。

//前序遍历:
算法实现:前序遍历顺序为中左右。需要传入root根节点,一个List进行接收遍历后的有序节点。终止条件是当root == null 说明到了叶子节点，结束递归。每次递归的逻辑:中左右，将val放入List中，先遍历左孩子再遍历右孩子。

//代码
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
     List<Integer> list =  new ArrayList<Integer>();
    preTree(root,list);
    return list;

    }

    public void preTree(TreeNode root,List<Integer>  list) {
        if(root == null){
            return;
        }
        list.add(root.val);
        preTree(root.left,list);
        preTree(root.right,list);
    } 
}

//中序 左中右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> list =  new ArrayList<Integer>();
    midTree(root,list);
    return list;
    }

    public void midTree(TreeNode root,List<Integer>  list) {
        if(root == null){
            return;
        }
        midTree(root.left,list);
        list.add(root.val);
        midTree(root.right,list);
    } 
}

//后序 左右中
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    postTree(root,list);
    return list;
    }

    public void postTree(TreeNode root,List<Integer> list){
        if(root == null) {
            return;
        }

        postTree(root.left,list);
        postTree(root.right,list);
        list.add(root.val);

    }
}

//迭代法 栈模拟
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root == null){
            return list;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right != null){
                stack.push(node.right);    
            } 
            if(node.left != null) {
                stack.push(node.left);
            }
        }
        return list;

    }
}
//中序遍历 迭代法访问和处理是两个过程,先把左子树处理完之后，弹出左子树最后一个叶子节点，进行处理。如果有右子树则对其在进行遍历,如果没有则弹出上一节点，再次进行处理。
//访问和处理是两个过程，先访问中间节点但是不处理

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list =  new ArrayList<Integer>();
    if (root == null) {return list;}
    Stack<TreeNode> stack = new Stack<TreeNode>();
     TreeNode node = root;
     while(node != null || !stack.isEmpty()) {
     if (node != null) {
         stack.push(node);
         node = node.left;
         }else {
         node = stack.pop();
         list.add(node.val);
         node = node.right;
         }
         
      }
    return list;
    }
}


// 后序遍历顺序：左-右-中，入栈顺序：
public class PostorderTraversal {
    
    private List<Integer> result = new ArrayList<Integer>();
    
    /**
     * 迭代实现，使用栈实现，出栈得到节点顺序为根右左，每次向list最开头插入元素
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null)
            return result;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);   //首先将根节点压栈
        while(!stack.isEmpty()) {
            TreeNode node  = stack.pop(); //首先出栈的为根节点，其后先出右子节点，后出左子节点
            if(node.left != null)
                stack.push(node.left);  //将左子节点压栈
            if(node.right != null) {
                stack.push(node.right); //将右子节点压栈
            }
            result.add(0, node.val); //因为出栈顺序为“根右左”，所以需要每次将元素插入list开头
        }
        return result;
    }
}