栈与递归紧密的联系

Algorithm

系统栈与递归之间的联系 ,以及用栈来模拟系统栈写出非递归程序

系统栈与递归之间的关系

图解系统栈与递归之间的关系：

原理
原理
原理
原理
原理
原理
原理
原理
原理
原理
原理

用栈来模拟系统栈 写出非递归程序

举个栗子 leetcode 144 Binary Tree Preorder Traversal:题目链接
递归遍历写法 AC:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> array = new ArrayList<Integer>();
        preorderTraversal( root , array);
        return array;
    } 
    
    public void preorderTraversal(TreeNode root, List<Integer> array) {
        if (root != null) {
            array.add(root.val);
            preorderTraversal(root.left, array);
            preorderTraversal(root.right, array);
        }
    }
}

用栈来模拟系统栈 非递归 AC (推荐)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

// 指令
class Command{
    String s;   // go:访问   print：打印
    TreeNode node;
    public Command(String s, TreeNode node){
        this.s = s;
        this.node = node;
    }
}

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();  
        if (root == null) {
            return res;
        }
        Stack<Command> stack = new Stack<Command>();
        stack.push(new Command("go", root));        
        while (stack.size() != 0) {
            Command com = stack.pop();
            if (com.s.equals("print")) {
                res.add(com.node.val);
            }else{
                assert(com.s.equals("go"));     
                if (com.node.right != null) {
                    stack.push(new Command("go", com.node.right));
                }
                if (com.node.left != null) {
                    stack.push(new Command("go", com.node.left));
                }
                stack.push(new Command("print", com.node));    // 更改此句的位置 变成中序  后序
            }
        }
        return res;
    }
}

leetcode 94. Binary Tree Inorder Traversal:题目链接

leetcode 145. Binary Tree Postorder Traversal:题目链接

本文标题:栈与递归紧密的联系

文章作者:XerDemo

发布时间:2018-11-18, 14:55:49

最后更新:2019-02-21, 16:44:50

原始链接:https://xerdemo.github.io/2018/11/18/栈与递归紧密的联系/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 系统栈与递归之间的关系
  2. 2. 用栈来模拟系统栈 写出非递归程序
|