二叉树的遍历

这里更新一下树的遍历方式，增加了一部分思想和 Golang 代码

前序遍历

这里说一下前序遍历的迭代写法，其实要写前序遍历的迭代写法首先要了解遍历的路程，其实我们无论是前序遍历、中序遍历、后序遍历，其实都是有一个相同的路径的，这个可以去找一下其余的博客

路径的遍历都是有往左靠拢的趋势，所以我们在写代码的时候体现出来就可以，在代码中体现如下：不断的往栈中放入左边的节点，这样的话就可以先行访问到。

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func preorderTraversal(root *TreeNode) []int {
    var (
        stack = make([]*TreeNode,0,10)
        curr = root
        res = make([]int,0,10)
    )
    for curr!=nil || len(stack) != 0{
        if curr!=nil{
            res = append(res,curr.Val)
            stack = append(stack,curr)
            curr = curr.Left
        }else{
            curr = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            curr = curr.Right
        }
    }
    return res
}

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> s = new Stack<>();
    TreeNode cur = root;
    while(cur != null || !s.isEmpty()){
        if(cur != null){
            res.add(cur.val); // root
            s.push(cur); 
            cur = cur.left; // left
        }else{
            cur = s.pop();
            cur = cur.right; // right
        }
    }
    return res;
}

中序遍历

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

后序遍历

// 前序遍历顺序为：根 -> 左 -> 右
// 后序遍历顺序为：左 -> 右 -> 根
// 所以, 我们可以把前序遍历的稍作修改: 根 -> 右 -> 左, 
// 然后结果存放到栈里进行倒序, 之后再遍历结果栈就可以输出后序遍历了
public List<Integer> postorderTraversal(TreeNode root) {
    Stack<TreeNode> s = new Stack<>();
    Stack<TreeNode> resStack = new Stack<>();
    TreeNode cur = root;
    while(cur != null || !s.isEmpty()){
        if(cur != null){
            resStack.push(cur); // root
            s.push(cur); 
            cur = cur.right; // right
        }else{
            cur = s.pop();
            cur = cur.left; // left
        }
    }

    List<Integer> res = new ArrayList<>();
    while(!resStack.isEmpty()){
        res.add(resStack.pop().val);
    }
    return res;
}