leecode刷题（25）-- 二叉树的层序遍历

leecode刷题（25）-- 二叉树的层序遍历

二叉树的层序遍历

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

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

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

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

---

思路

这道题我们可以定义三个列表：当前层列表，下一层列表，新列表。 先遍历当前层，将当前层的节点加入新列表，当前层的左右节点加入下一层列表，再将下一层列表添加的节点也加入新列表，然后互换当前层和下一层，直到当前层和下一层为空，返回新列表。

代码如下

java描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList();
        List<TreeNode> list = new ArrayList() {{
            this.add(root);
        }};
        if (root == null) return result;
        while (!list.isEmpty()) {
            List<Integer> curList = new ArrayList();
            List<TreeNode> nextList = new ArrayList();
            for (TreeNode cur: list){
                curList.add(cur.val);
                if (cur.left != null)   nextList.add(cur.left);
                if (cur.right != null)  nextList.add(cur.right);
            }
            list = nextList;
            result.add(curList);
        }
        return result;
    }
}

python描述

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res = []
        cur_nodes = [root]
        next_nodes = []
        res.append([i.val for i in cur_nodes])
        while cur_nodes or next_nodes:
            for node in cur_nodes:
                if node.left:
                    next_nodes.append(node.left)
                if node.right:
                    next_nodes.append(node.right)
            if next_nodes:
                res.append([i.val for i in next_nodes])
            
            cur_nodes = next_nodes
            next_nodes = []
        
        return res

总结

很明显，上述代码中，python 版本的代码更为简洁明了，根据我们的思路来很容易就能写出代码，python 中的定义列表和列表生成式用得真是舒服，java 略微繁琐一点，但是性能比python好，算是各有优缺点吧。

对比.png