花式玩转二叉树遍历，递归迭代应有尽有，绝对满足您的需求！！！

发表于

小知识，大挑战！本文正在参与“ 程序员必备小知识 ”创作活动

本文同时参与 「掘力星计划」 ，赢取创作大礼包，挑战创作激励金

Code皮皮虾 一个沙雕而又有趣的憨憨少年，和大多数小伙伴们一样喜欢听歌、游戏，当然除此之外还有写作的兴趣，emm…，日子还很长，让我们一起加油努力叭🌈

如果觉得写得不错的话，球球一个关注哦😉

前言

二叉树遍历对应地址：

力扣：二叉树前序遍历地址

力扣：二叉树中序遍历地址

力扣：二叉树后序遍历地址

力扣：二叉树层序遍历地址

二叉树层序遍历

使用广度优先搜索（BFS）

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
47
48
49
50
51
52
java复制代码public class Main {



    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;

        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(list);
        }

        return res;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

在这里插入图片描述

递归法

二叉树前序遍历

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
java复制代码
public class Main {


    List<Integer> res;
    public List<Integer> preorderTraversal(TreeNode root) {
        res = new ArrayList<>();
        if(root == null)
            return res;
        preTreeNode(root);
        return res;
    }

    private void preTreeNode(TreeNode root) {
        if(root == null) return;

        res.add(root.val);

        preTreeNode(root.left);
        preTreeNode(root.right);
    }

}

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

在这里插入图片描述
复杂度分析

  • 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
  • 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

二叉树中序遍历

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
java复制代码public class Main {


    List<Integer> res;

    public List<Integer> inorderTraversal(TreeNode root) {
        res = new ArrayList<>();
        if (root == null)
            return res;

        midTreeNode(root);
        return res;
    }

    private void midTreeNode(TreeNode root) {
        if (root == null) return;

        midTreeNode(root.left);

        res.add(root.val);

        midTreeNode(root.right);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

在这里插入图片描述

二叉树后序遍历

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
java复制代码public class Main {
    

    List<Integer> res;
    public List<Integer> postorderTraversal(TreeNode root) {
        res = new ArrayList<>();
        if(root == null)
            return res;

        postTreeNode(root);
        return res;
    }

    private void postTreeNode(TreeNode root) {
        if(root == null) return;

        postTreeNode(root.left);
        postTreeNode(root.right);

        res.add(root.val);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

在这里插入图片描述

迭代法

二叉树前序遍历

与递归方法相差无几，只是把递归中隐藏的栈显示出来

因为栈的特性，我们需要先把右子节点push到栈中，再push左子节点，这样拿出来的时候就是先拿出左子节点。

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
java复制代码
public class Main {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return res;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

在这里插入图片描述

二叉树中序遍历

中序遍历式按 左 中 右的顺序输出节点。
所以我们尽可能的把节点的左子树压入栈中，这样栈顶元素为最左侧节点
在pop出来后，将其右子节点push进去，这样的话就是按照中序遍历获取元素啦

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
java复制代码
public class Main {


    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.right != null) {
                cur = node.right;
            }
        }
        return res;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

在这里插入图片描述

二叉树后序遍历

  • 首先将根节点压栈
  • 因为先出栈的为根节点，其后先出右子节点，最后出左子节点
  • 将左子节点压栈
  • 将右子节点压栈
  • 因为出栈顺序为“根右左”，所以需要每次将元素插入list开头
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
java复制代码public class Main {


    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null)
            return result;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);   
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop(); 
            if (node.left != null)
                stack.push(node.left);  
            if (node.right != null) {
                stack.push(node.right); 
            }
            result.add(0, node.val); 
        }
        return result;

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

💖最后

我是 Code皮皮虾，一个热爱分享知识的 皮皮虾爱好者，未来的日子里会不断更新出对大家有益的博文，期待大家的关注！！！

创作不易，如果这篇博文对各位有帮助，希望各位小伙伴可以一键三连哦！，感谢支持，我们下次再见~

一键三连.png

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%