[Leetcode][Python/Java]Binary Tree Level Order Traversal/二叉树层序遍历

桃扇骨 2022-06-12 08:38 159阅读 0赞

## 题目大意 ##

实现树的广度优先遍历，每一层上的数据按照从左到右的顺序排列。

## 解题思路 ##

参考：[链接][Link 1]  
将树每一层的节点存在一个列表中，遍历列表中的元素，如果该节点有左右节点的话，就把它们加入一个临时列表，这样当遍历结束时，下一层的节点也按照顺序存储好了，不断循环直到下一层的列表为空。

## 代码 ##

### Java ###

import java.util.*;
    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            if (root == null) {
                return new ArrayList<>();
            }
    
            ArrayList<Integer> result = new ArrayList<>();
            Deque<TreeNode> deque = new LinkedList<>();
            deque.add(root);
            while (!deque.isEmpty()) {
                TreeNode t = deque.pop();
                if (t.left != null) {
                    deque.add(t.left);
                }
                if (t.right != null) {
                    deque.add(t.right);
                }
                result.add(t.val);
            }
            return result;
        }
    }

### Python ###

#### 迭代 ####

![BFS][]

class Solution(object):
        def levelOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            tree = []
            if not root:
                return tree
            curr_level = [root]
            # print(type(root), type(curr_level))  # (<class 'precompiled.treenode.TreeNode'>, <type 'list'>)
            # print(curr_level)  # 作为list，却并不能遍历整个树
            while curr_level:
                level_list = []
                next_level = []
                for temp in curr_level:
                    level_list.append(temp.val)
                    if temp.left:
                        next_level.append(temp.left)
                    if temp.right:
                        next_level.append(temp.right)
                tree.append(level_list)
                curr_level = next_level
            return tree

补充：

#### 递归 ####

class Solution(object):
        def preorder(self, root, level, res):
            if root:
                if len(res) < level+1: res.append([])
                res[level].append(root.val)
                self.preorder(root.left, level+1, res)
                self.preorder(root.right, level+1, res)
                
        def levelOrder(self, root):
            res=[]
            self.preorder(root, 0, res)
            return res

## 总结 ##

1.  正如代码注释，将root外面加括号使得其变为了list。但在下面的for循环中，依然其是作为一个树结构存储的，是否可以理解为这里的括号仅仅是将他变得可被遍历。  
    之后我`print(temp)`得到了：

<precompiled.treenode.TreeNode object at 0x7fbb9a294b50>
    <precompiled.treenode.TreeNode object at 0x7fbb9a294d50>
    <precompiled.treenode.TreeNode object at 0x7fbb9a294d90>
    <precompiled.treenode.TreeNode object at 0x7fbb9a294dd0>
    <precompiled.treenode.TreeNode object at 0x7fbb9a294e10>

说明确实里面还是树结构。  
应该用这个解释来理解，[廖雪峰-迭代][-]，可以再看一遍。

[Link 1]: https://shenjie1993.gitbooks.io/leetcode-python/102%20Binary%20Tree%20Level%20Order%20Traversal.html
[BFS]: /images/20220612/0b16159841f74ed1a25f4b1e5ef7f9fe.png
[-]: https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/0014317793224211f408912d9c04f2eac4d2af0d5d3d7b2000