能力随心，自然成长

0%

二叉树——几种遍历的非递归模板

发表于 更新于 分类于

二叉树遍历的递归代码比较精简，非递归的迭代思路也常常在leetcode中遇到，本文整理了几种非递归的java代码作为模板。

前序遍历

二叉树的前序遍历-leetcode-144

1
class Solution {
2
    public class TreeNode {
3
        int val;
4
        TreeNode left;
5
        TreeNode right;
6
        TreeNode(int x) {
7
            val = x;
8
        }
9
    }
10
    public List<Integer> preorderTraversal(TreeNode root) {
11
        List<Integer> list = new LinkedList<>();
12
        Stack<TreeNode> stack = new Stack<>();
13
        if (root == null) return list;
14
        stack.push(root); //根结点入栈
15
        TreeNode p;
16
        while (!stack.empty()) {
17
            p = stack.pop();
18
            list.add(p.val);
19
            if (p.right != null) { //右节点先入栈 后出
20
                stack.push(p.right);
21
            }
22
            if (p.left != null) {
23
                stack.push(p.left);
24
            }
25
        }
26
        return list;
27
    }
28
}

中序遍历

二叉树的中序遍历-leetcode-94

1
class Solution {
2
    public class TreeNode {
3
        int val;
4
        TreeNode left;
5
        TreeNode right;
6
        TreeNode(int x) {
7
            val = x;
8
        }
9
    }
10
    public List<Integer> inorderTraversal(TreeNode root) {
11
        List<Integer> ans = new ArrayList<>();
12
        Stack<TreeNode> stack = new Stack<>();
13
        TreeNode p = root;
14
        while (p != null || !stack.isEmpty()) {
15
            while (p != null) {
16
                stack.push(p);
17
                p = p.left;
18
            }
19
            p = stack.pop();
20
            ans.add(p.val);
21
            p = p.right;
22
        }
23
        return ans;
24
    }
25
}

后序遍历

二叉树的后序遍历-leetcode-145

1
class Solution{
2
    public class TreeNode {
3
        int val;
4
        TreeNode left;
5
        TreeNode right;
6
        TreeNode(int x) {
7
            val = x;
8
        }
9
    }
10
    // 利用一个指针标记访问过的右子树结点 当访问过右子树在访问根结点
11
    public List<Integer> postorderTraversal(TreeNode root) {
12
        Stack<TreeNode> stack = new Stack<>();
13
        List<Integer> list = new LinkedList<>();
14
        if (root == null) return list;
15
        TreeNode p = root, r = null; //r结点用来表示当前的左孩子是否被访问
16
        while (!stack.empty() || p != null) {
17
            while (p != null) {
18
                stack.push(p);
19
                p = p.left;
20
            } //走到最左边的结点
21
            p = stack.peek();
22
            if (p.right != null && p.right != r) { 
23
                //存在右子树并且没有被访问则先访问右子树，否则访问该节点
24
                stack.push(p.right);
25
                p = p.right;
26
                p = p.left;
27
            } else {
28
                p = stack.pop();
29
                list.add(p.val);
30
                r = p;
31
                p = null; //让p指针不要乱指
32
            }
33
        }
34
        return list;
35
    }
36
    /*前序：根->左->右 
37
    后序：左->右->根 
38
    后序翻转  根->右->左 把后序当作前序然后在翻转一次 （不是严格意义的后序遍历）*/
39
    public List<Integer> postorderTraversal_1(TreeNode root) {
40
        Stack<TreeNode> stack = new Stack<>();
41
        List<Integer> list = new LinkedList<>();
42
        if (root == null) return list;
43
        stack.push(root);
44
        while (!stack.empty()) {
45
            TreeNode p = stack.pop();
46
            list.add(0, p.val);
47
            if (p.left != null) {
48
                stack.push(p.left);
49
            }
50
            if (p.right != null) {
51
                stack.push(p.right);
52
            }
53
        }
54
        return list;
55
    }
56
    
57
    //阿里面试题
58
    /*仅利用栈去判断该节点是否为父结点，创新性思路是每次在栈中压入父节点后压入null节点，
59
    之后再依次压入右子节点和左子节点。*/
60
    public List<Integer> postorderTraversal_2(TreeNode root) {
61
        Stack<TreeNode> stack = new Stack<>();
62
        List<Integer> list = new ArrayList<>();
63
        if (root == null) return list;
64
        stack.push(root);
65
        while (!stack.empty()) {
66
            TreeNode p = stack.peek();
67
            if (p == null) {
68
                stack.pop();
69
                list.add(stack.pop().val);
70
            } else {
71
                stack.push(null);
72
                if (p.right != null) {
73
                    stack.push(p.right);
74
                }
75
                if (p.left != null) {
76
                    stack.push(p.left);
77
                }
78
            }
79
        }
80
        return list;
81
    }
82
}

层序遍历

二叉树的层序遍历 (leetcode-102)

1
class Solution {
2
    public class TreeNode {
3
        int val;
4
        TreeNode left;
5
        TreeNode right;
6
        TreeNode(int x) {
7
            val = x;
8
        }
9
    }
10
	//1.借用辅助栈
11
    public List<List<Integer>> levelOrder(TreeNode root) {
12
        List<List<Integer>> res = new ArrayList<>();
13
        Queue<TreeNode> queue = new LinkedList<>();
14
        if (root == null) return res;
15
        queue.add(root);
16
        while (!queue.isEmpty()) {
17
            int count = queue.size(); //记录当前层的个数
18
            List<Integer> list = new ArrayList<>();
19
            while (count > 0) {
20
                TreeNode node = queue.poll();
21
                list.add(node.val); //当前层的节点加入该list
22
                if (node.left != null)
23
                    queue.add(node.left);
24
                if (node.right != null)
25
                    queue.add(node.right);
26
                count--;
27
            }
28
            res.add(list);
29
        }
30
        return res;
31
    }
32
       
33
    //2.递归思路
34
   public List<List<Integer>> levelOrder_2(TreeNode root) {
35
        List<List<Integer>> ans = new ArrayList<>();
36
        DFS(root, 0, ans);
37
        return ans;
38
    }
39
    //通过列表的长度来确认是否添加子列表  列表的长度就是二叉树的高度
40
    public void DFS(TreeNode p, int level, List<List<Integer>> ans) {
41
        if (p == null) {
42
            return;
43
        }
44
        if (ans.size() <= level) {
45
            List<Integer> list = new ArrayList<>();
46
            ans.add(list);
47
        }
48
        ans.get(level).add(p.val);
49
        DFS(p.left, level + 1, ans);
50
        DFS(p.right, level + 1, ans);
51
    } 
52
}