【左神算法】二叉树的先序、中序、后序遍历，包括递归方式和非递归方式

二叉树的先序、中序、后序遍历，包括递归方式和非递归方式

1、二叉树的前序遍历

1.1 思路:

二叉树是一个由left子节点和right子节点 以及val组成的数据结果。而前序遍历的过程就是 根左右。
而实现前序遍历，我们可以用两种方式一种是递归实现，先添加val,递归左右子节点。一种非递归实现，
递归的实现就是系统帮我们自行压栈操作，因此可以借助栈结构来实现。先添加root节点，当栈不为null 保存root.val 以及压入左子节点和右子节点。如此反复。
时间复杂度:二叉树的遍历需要花费O(n) 如果不计算栈的消耗
空间复杂度:O(n) 无论是递归还是非递归 都需要进行O(n)

1.2 递归实现 code

 //栈
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>(); 
        if(root == null)    return res;

        Stack<TreeNode> stack = new Stack();
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);

            if(node.right!=null){
                stack.push(node.right);
            }

            if(node.left != null){
                stack.push(node.left);
            }            
        }  
        return res;
    }

1.3 非递归实现 code

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)    return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.right != null){
                stack.push(node.right);
            }

            if(node.left != null){
                stack.push(node.left);
            }
        }
        return res;
    }

2、二叉树的中序遍历

2.1 思路:

中序遍历和前序遍历的递归版相似，只需要修改添加的位置。
而非递归版借助栈 先压入左子节点，如果左子节点为null 弹出 添加值，然后查看右子节点。
时间复杂度:O(n)
空间复杂度:O(n)

2.2 递归实现 code

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList();
        helper(root,result);
        return result;
    }

    public static void helper(TreeNode root,List<Integer> result){
        if(root!=null){
            //左
            if(root.left!=null){
                helper(root.left,result);
            }
            //中
            result.add(root.val);
            //右
            if(root.right!=null){
                helper(root.right,result);
            }
        }
    }

2.3 非递归实现 code

	//借助stack
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)    return res;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while( cur!=null || !stack.empty()){
            //添加左节点
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            //push右节点
            cur = cur.right;
        }
        return res;
    }

3、二叉树的后序遍历

3.1 思路:

递归版 直接 修改add的位置
非递归版 后序遍历 为 左右根 而前序遍历为根左右 有没有发现 如果将左右的位置改变 然后在逆序就是后序遍历的结果了。这里借助两个栈。一个栈存储节点，另一个栈存储数据，将根右左的值添加 然后pop 就是结果。
时间复杂度:O(n)
空间复杂度:O(n)

3.2 递归实现 code

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)    return res;
        helper(root,res);
        return res;
    }

    public void helper(TreeNode node,List<Integer> res){
        if(node!=null){
            if(node.left!=null){
                helper(node.left,res);
            }

            if(node.right!=null){
                helper(node.right,res);
            }
            res.add(node.val);
        }
    }

3.3 非递归实现 code

	//左右根   先序遍历 根左右    根右左 
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null)  return res;
        Stack<Integer> stack = new Stack();//存储数据
        Stack<TreeNode> nodeStack = new Stack();//存储节点

        nodeStack.push(root); //先存储根节点
        while(!nodeStack.isEmpty()){
            TreeNode node = nodeStack.pop();
            stack.push(node.val);
            if(node.left!=null){
                nodeStack.push(node.left);
            }

            if(node.right!=null){
                nodeStack.push(node.right);
            }
        }
        while(!stack.isEmpty()){
            res.add(stack.pop());
        }
        return res;
    }