二叉树遍历

前序遍历 pre-order:中左右
中序遍历 in-order:左中右（遍历后有序）
后续遍历 post-order:左右中

1、万金油写法，利用递归，时候前、中、后序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null){
            return new ArrayList();
        }
        List<Integer> leftNode = inorderTraversal(root.left);
        List<Integer> rightNode = inorderTraversal(root.right);

        List<Integer> result = new ArrayList();
        // 前序遍历
        result.add(root.val);
        result.addAll(leftNode);
        result.addAll(rightNode);

        // 中序遍历
        //result.addAll(leftNode);
        //result.add(root.val);
        //result.addAll(rightNode);

        // 后序遍历
        //result.addAll(leftNode);
        //result.addAll(rightNode);
        //result.add(root.val);
        return result;
    }
}

非递归实现，使用栈

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList();
        if(root == null){
            return result;
        }
        
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            //前序遍历，栈先进后出，这里要先放右节点，后方左节点
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
        
    }
}