Day 13 二叉树part01

二叉树的递归遍历

这个用递归就好，现在写起来基本没问题

二叉树的迭代遍历

这个是重点，今天写的时候居然一次写出来了，多刷还是有用的。前中后三种遍历方式，其迭代版本的难度排序 前 < 中 < 后。所以写的时候也是按这个顺序去做的。

144. 二叉树的前序遍历

使用一个栈来存储需要遍历的节点，注意，当遍历一个节点后，我们需要先将其右节点压栈再压栈左节点，这样可以保证先遍历左子树再右子树。

class Solution {
    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 tmp = stack.pop();
            res.add(tmp.val);
            if(tmp.right != null) stack.push(tmp.right);
            if(tmp.left != null) stack.push(tmp.left);
        }
        return res;
    }
}

94. 二叉树的中序遍历

class Solution {
    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.isEmpty()){   //cur代表要遍历的节点
            while(cur != null){  //一直向左走，一直到null
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();  //此时从栈中弹出的节点一定是最左的，因此可以遍历它了
            res.add(cur.val);
            cur = cur.right;  //当该节点遍历完，就应该去遍历其右子树
        }
        return res;
    }
}

145. 二叉树的后序遍历

与中序遍历非常相似，一定要比较着学。

与中序的不同之处在于：

• 中序遍历中，从栈中弹出的节点，其左子树是访问完了，可以直接访问该节点，然后接下来访问右子树。
• 后序遍历中，从栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。

因此，我们在后序遍历中，引入了一个pre来记录历史访问记录。

• 当访问完一棵子树的时候，我们用pre指向该节点。
• 这样，在回溯到父节点的时候，我们可以依据pre是指向左子节点，还是右子节点，来判断父节点的访问情况。

while(!stack.isEmpty() || cur != null)对于中序遍历和后序遍历判断条件的理解：

• 对于左子树访问和右子树访问是不同的，当访问一个节点的时候，我们会从该节点开始，压栈并一直向左走，直到没有左子树才去弹栈，然后转向去访问右子树

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root, pre = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){ //和中序遍历完全一致，走到最左即可
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if(cur.right == null || cur.right == pre) { 
                //如果一个节点没有右子树，或者右子树已经遍历过，那么这个节点就可以被访问了
                res.add(cur.val);
                pre = cur;
                cur = null;
            }else{ //右子树还没遍历，先将cur还原回栈中，转而遍历右子树
                stack.push(cur);
                cur = cur.right;
            }
            
        }
        return res;
    }
}