二叉树遍历

根左右

1、递归

    List list = new ArrayList<>();
    public List preorderTraversal(TreeNode root) {
        pre(root);
        return list;
    }

    public void pre(TreeNode root) {
        if(root == null) {
            return;
        }
        list.add(root.val);
        pre(root.left);
        pre(root.right);
    }

2、迭代

使用栈第一次访问节点的时候，就把节点的值添加到list里面。

    public List preorderTraversal(TreeNode root) {
        Deque stack = new LinkedList<>();
        List list = new ArrayList<>();

        while(root != null || !stack.isEmpty()) {
            while(root != null) {
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            root = root.right;
        }

        return list;
    }

左根右（对于二叉搜索树来说，中序遍历是有序的序列）

1、递归

	List list = new ArrayList<>();
    
    public List inorderTraversal(TreeNode root) {
        in(root);
        return list;
    }

    public void in(TreeNode root) {
        if(root == null) return;

        in(root.left);
        list.add(root.val);
        in(root.right);
    }

2、迭代

中序遍历的顺序是左根右，所以从跳出循环开始向list里面添加数值。

    public List inorderTraversal(TreeNode root) {
        Deque stack = new LinkedList<>();
        List list = new ArrayList<>();

        while(!stack.isEmpty() || root != null) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }

        return list;
    }

左右根

1、递归

    List list = new ArrayList<>();

    public List postorderTraversal(TreeNode root) {
        post(root);
        return list;
    }

    public void post(TreeNode root) {
        if(root == null) return;

        post(root.left);
        post(root.right);
        list.add(root.val);
    }

2、迭代

使用pre存储前驱节点，只有当前节点没有右孩子或者右孩子已经被访问过了，才把当前节点的值添加到lis里面；
否则当前节点入栈，访问当前节点的右子树。

    public List postorderTraversal(TreeNode root) {
        Deque stack = new LinkedList<>();
        List list = new ArrayList<>();
        TreeNode pre = null;

        while(!stack.isEmpty() || root != null) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            if(root.right == null || pre == root.right) {
                list.add(root.val);
                pre = root;
                root = null;
            }else{
                stack.push(root); 
                root = root.right;
            }
        }

        return list;
    }