力扣算法学习day09-1

力扣算法学习day09-1

二叉树的遍历 迭代法---统一逻辑版本（题目略，补充昨日）

144-二叉树的前序遍历94-二叉树的中序遍历145-二叉树的后序遍历

已复习 59-螺旋矩阵

// 迭代法：逻辑统一版
    public List preorderTraversal(TreeNode root) {
        // ArrayDeque stack = new ArrayDeque<>();// ArrayDeque不能添加null值做元素
        linkedList stack = new linkedList<>();
        ArrayList result = new ArrayList<>();

        if(root == null){
            return result;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node != null){
                if(node.right != null){
                    stack.push(node.right);
                }
                if(node.left != null){
                    stack.push(node.left);
                }

                stack.push(node);
                stack.push(null);
            } else{
                node = stack.pop();
                result.add(node.val);
            }
        }
        return result;
    }

// 迭代法：逻辑统一版
    public List inorderTraversal(TreeNode root) {
        // ArrayDeque stack = new ArrayDeque<>();// ArrayDeque不能添加null值做元素
        linkedList stack = new linkedList<>();
        ArrayList result = new ArrayList<>();

        if(root == null){
            return result;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node != null){
                if(node.right != null){
                    stack.push(node.right);
                }
                
                stack.push(node);
                stack.push(null);

                if(node.left != null){
                    stack.push(node.left);
                }
            } else{
                node = stack.pop();
                result.add(node.val);
            }
        }
        return result;
    }

// 迭代法：逻辑统一版
    public List postorderTraversal(TreeNode root) {
        // ArrayDeque stack = new ArrayDeque<>();// ArrayDeque不能添加null值做元素
        linkedList stack = new linkedList<>();
        ArrayList result = new ArrayList<>();

        if(root == null){
            return result;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node != null){
                stack.push(node);
                stack.push(null);

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

                if(node.left != null){
                    stack.push(node.left);
                }
            } else{
                node = stack.pop();
                result.add(node.val);
            }
        }
        return result;
    }