LeetCode：102. Binary Tree Level Order Traversal（二叉树的层次遍历）

àì夳堔傛蜴生んèń 2022-04-04 12:38 171阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录**

题目描述：

java实现方法1：深度优先（递归算法）

python实现方式1：

java实现方法2：一种非递归的方式，利用栈的形式

python实现方式2：

源码github地址：https://github.com/zhangyu345293721/leetcode

--------------------

### 题目描述： ###

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:  
给定二叉树: \[3,9,20,null,null,15,7\],

3
       / \
      9  20
        /  \
       15   7

返回其层次遍历结果：

[
      [3],
      [9,20],
      [15,7]
    ]

来源：力扣（LeetCode）

--------------------

### java实现方法1：深度优先（递归算法） ###

/**
         * 二叉树层次遍历
         *
         * @param root 根节点
         * @return 返回遍历链表
         */
        public List<List<Integer>> levelOrder(TreeNode root) {
            if (root == null) {
                return new ArrayList<>();
            }
            List<List<Integer>> res = new ArrayList();
            levelOrderHelper(res, root, 0);
            return res;
        }
    
        /**
         * 递归遍历
         *
         * @param res    结果链表
         * @param root   根节点
         * @param height 高度
         */
        public void levelOrderHelper(List<List<Integer>> res, TreeNode root, int height) {
            if (root == null) {
                return;
            }
            if (height >= res.size()) {
                res.add(new LinkedList<>());
            }
            res.get(height).add(root.val);
            levelOrderHelper(res, root.left, height + 1);
            levelOrderHelper(res, root.right, height + 1);
        }

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### python实现方式1： ###

def level_helper(self, res: List[List[int]], root: TreeNode, height: int):
            '''
                循环遍历二叉树
            Args:
                res: 链表
                root: 根节点
                height: 高度
            '''
            if not root:
                return
            if height >= len(res):
                res.append([])
            res[height].append(root.val)
            self.level_helper(res, root.left, height + 1)
            self.level_helper(res, root.right, height + 1)
    
        def level_order1(self, root: TreeNode) -> List[List[int]]:
            '''
                二叉树层次遍历
            Args:
                root: 跟节点
            Returns:
                层次遍历返回值
            '''
            if not root:
                return []
            res = []
            self.level_helper(res, root, 0);
            return res

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### java实现方法2：一种非递归的方式，利用栈的形式 ###

/**
         * 二叉树层次遍历
         *
         * @param root 根节点
         * @return 返回遍历链表
         */
        public List<List<Integer>> levelOrder2(TreeNode root) {
            if (root == null) {
                return new ArrayList<>();
            }
            List<List<Integer>> res = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                List<Integer> tempList = new ArrayList();
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode p = queue.poll();
                    tempList.add(p.val);
                    if (p.left != null) {
                        queue.add(p.left);
                    }
                    if (p.right != null) {
                        queue.add(p.right);
                    }
                }
                res.add(tempList);
            }
            return res;
        }

时间复杂度：O(n^2)

空间复杂度：O(n)

--------------------

### python实现方式2： ###

def level_order2(self, root: TreeNode) -> List[List[int]]:
            '''
                找出抢劫最大值
            Args:
                root: 跟节点
            Returns:
                最大值
            '''
            if not root:
                return []
            res = []
            queue = []
            queue.append(root)
            while len(queue) > 0:
                arr = []
                size = len(queue)
                for i in range(size):
                    p = queue.pop(0)
                    arr.append(p.val)
                    if p.left:
                        queue.append(p.left)
                    if p.right:
                        queue.append(p.right)
                res.append(arr)
            return res

时间复杂度：O(n^2)

空间复杂度：O(n)

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode