二叉树的遍历

二叉树遍历的路径 : 前中后序二叉树遍历的路劲是一样的!
前序 : 根 -左子树-右子树 在非递归的视角: 在第一次到达这个节点就直接操作这个节点!
中序 : 左子树-根-右子树 在非递归的视角: 在第二次到达这个节点再操作这个节点!
后续 : 左子树-右子树-根 在非递归的视角: 在第三次到达这个节点再操作这个节点!

前序

// 非递归实现二叉树前序遍历  
    // 具体过程 
    // 为了先 左 再 右 // 所以先放右 再放左  
    // 模拟递归额过程 
    // 先将根节点入栈 
    // 再将栈顶pop() 并判断 抛出节点 左右子节点是否为空 
    // 如果 1. 右子节点不为空 将右子节点入栈 
    //       2.如果左子节点不为空 将左子节点入栈
    // 循环上面三步 直到栈为空 ;
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return ans;

        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            ans.add(cur.val); // 在第一次访问到当前节点就直接把当前节点遍历
            if(cur.right != null){
                stack.push(cur.right);
            }
            if(cur.left != null){
                stack.push(cur.left);
            }
        }
        return ans;
    }

中序

 // 左 根 右 
    // 先循环向左 将所有左边的入栈 （直到左子树为 null ）
    // 依次出栈访问 并检查其右子树为不为空 不为空就入栈 继续向左找
    // 循环前两步
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return ans;
        while(true){
            while(root != null){
                stack.push(root);
                root = root.left;
            }// 先将最左左边的元素 确定到栈顶 

             if(stack.isEmpty()){
                break;
            }// 抛出元时要判断栈是否为空 为空 则表示遍历完成
            root = stack.pop(); // 将最左节点抛出 
            ans.add(root.val);
            root = root.right;
        }
         return ans;
    }

后序

// 左 右 根
    // 非递归后序遍历 
    // 类似于中序遍历 
    // 1. 循环访问将左子树入栈 （直到最左边 ）
    // 2. 判断 栈顶元素是否可以被访问 条件 1: 栈顶元素 没有 左子树 可以被访问 2: 栈顶元素的上一个被访问的元素是 栈顶元素的右子树 可以访问 
    // 3. 循环从 栈顶元素的右子树开始 goto 1; 
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return ans;
        TreeNode cur = root;
        TreeNode pre = null;
        while(true){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            if(stack.isEmpty()){
                break;
            }
            TreeNode top = stack.peek();
            if(top.right == null || pre == top.right){
                stack.pop();
                pre = top;
                ans.add(top.val);
            }else 
                cur = top.right;
        }
        return ans;
     }