【LeetCode】栈、队列问题：用栈代替递归

「爱情、让人受尽委屈。」 2022-10-29 09:12 131阅读 0赞

### 模拟递归 ###

#### [144. 二叉树的前序遍历][144.] ####

难度中等508收藏分享切换为英文接收动态反馈

给你二叉树的根节点 `root` ，返回它节点值的 **前序** 遍历。

**示例 1：**

![在这里插入图片描述][20210210225856847.png]

输入：root = [1,null,2,3]
    输出：[1,2,3]

**示例 2：**

输入：root = []
    输出：[]

**示例 3：**

输入：root = [1]
    输出：[1]

**递归解法**

class Solution { 
        public List<Integer> preorderTraversal(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
            search(root , list);
            return list;
        }
    
        void search(TreeNode root , List<Integer> list){ 
            if(root != null){ 
                list.add(root.val);
                search(root.left , list);
                search(root.right ,list);
            }
        }
    
        
    }

**栈模拟解法**

*  通用解法（适用于前、中、后，因为教材传统的遍历解法，只能应对前序遍历）
 *  核心思想：因为自己模拟系统栈，无法做到返回到栈帧保存的执行位置，所以说那么可以把后续要执行的操作包装起来也压栈，即搞一个命令栈，命令中有不同字段区分不同操作

class Solution { 
        
        class Command{ 
            boolean isPrint;
            TreeNode node;
    
            Command(boolean isPrint , TreeNode node){ 
                this.isPrint = isPrint;
                this.node = node;
            };
        }
    
        public List<Integer> preorderTraversal(TreeNode root) { 
            List<Integer> res = new LinkedList<>();
            if(root == null){ 
                return res;
            }
    
            LinkedList<Command> stack = new LinkedList<>();
            stack.push(new Command(false , root));
    
            while(stack.size() != 0){ 
                Command cmd = stack.pop();
                if(cmd.isPrint){ 
                    res.add(cmd.node.val);
                }else { 
                    if(cmd.node.right != null){ 
                        stack.push(new Command(false , cmd.node.right));
                    }
                    if(cmd.node.left != null){ 
                        stack.push(new Command(false , cmd.node.left));
                    }
                    stack.push(new Command(true , cmd.node));
                }
            }    
    
            return res;
        }
    
    }

#### [94. 二叉树的中序遍历][94.] ####

难度中等851收藏分享切换为英文接收动态反馈

给定一个二叉树的根节点 `root` ，返回它的 **中序** 遍历。

**示例 1：**

![在这里插入图片描述][20210210225839671.png]

输入：root = [1,null,2,3]
    输出：[1,3,2]

**示例 2：**

输入：root = []
    输出：[]

**示例 3：**

输入：root = [1]
    输出：[1]

**递归**

class Solution { 
        public List<Integer> inorderTraversal(TreeNode root) { 
            List<Integer> res = new LinkedList<>();
            func(root , res);
            return res;
        }
    
        void func(TreeNode root , List<Integer> res){ 
            if(root != null){ 
                func(root.left , res);
                res.add(root.val);
                func(root.right ,res);
            }
        }
    }

**循环**

class Solution { 
        class Command{ 
            boolean isPrint;
            TreeNode node;
            Command(boolean isPrint , TreeNode node){ 
                this.isPrint = isPrint;
                this.node = node;
            };
        }
        public List<Integer> inorderTraversal(TreeNode root) { 
            List<Integer> res = new LinkedList<>();
            if(root == null){ 
                return res;
            }
    
            LinkedList<Command> stack = new LinkedList<>();
            stack.push(new Command(false , root));
    
            while(stack.size() != 0){ 
                Command cmd =stack.pop();
                if(cmd.isPrint){ 
                    res.add(cmd.node.val);
                }else{ 
                    if(cmd.node.right != null){ 
                        stack.push(new Command(false , cmd.node.right));
                    }
                    stack.push(new Command(true , cmd.node)); // 中序
                    if(cmd.node.left != null){ 
                        stack.push(new Command(false , cmd.node.left));
                    }
                }
            }
    
            return res;
        }
    }

[144.]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[20210210225856847.png]: /images/20221024/39a706cdd3fb4744b486896422444e5b.png
[94.]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
[20210210225839671.png]: /images/20221024/035d539b32d04195bf9702c6bc93785a.png