Binary Tree Level Order Traversal

题目描述

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:

Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

解题方法

• 用两个变量curNum和nextNum分别记录当前层和下一层的node数量，同时用另一个curList保存当前层的node
• 当current level的node数量减为0的时候，就表示这一层已经遍历完，讲curList加到result数组里，curList = nextNum, nextNum = 0, curList = []

Solution

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

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        queue = deque()
        result = []
        curList = []
        curNum = 1
        nextNum = 0
        queue.append(root)
        while queue:
            cur = queue.popleft()
            curNum -= 1
            curList.append(cur.val)
            if cur.left:
                queue.append(cur.left)
                nextNum += 1
            if cur.right:
                queue.append(cur.right)
                nextNum += 1
            if curNum == 0:
                curNum = nextNum
                nextNum = 0
                result.append(list(curList))
                curList = []

        return result

空间O(1)的做法

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

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        levelNum = self.maxDepth(root)
        results = []
        for i in range(levelNum):
            curLevel = []
            levelI = self.getNodesAtLevel(root, i, curLevel)
            results.append(curLevel)
        return results

    def getNodesAtLevel(self, root, level, curLevel):
        if not root or level < 0:
            return False
        if level == 0 and root:
            curLevel.append(root.val)
            return True
        left = self.getNodesAtLevel(root.left, level - 1, curLevel)
        right = self.getNodesAtLevel(root.right, level - 1, curLevel)
        return left or right

    def maxDepth(self, root):
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

上面是先求了depth，但是这样就多了遍历求depth的时间，可以不求depth,在getNodesAtLevel里，当某一层最终return False时，说明 这一层已经没有node,就可以break了

i = 0
while True:
    curLevel = []
    levelI = self.getNodesAtLevel(root, i, curLevel)
    if not levelI:
        break
    i += 1
    results.append(curLevel)

递归

还有递归的方法，贴上C++的参考

// 递归版,时间复杂度 O(n),空间复杂度 O(n) class Solution {
public:
      vector<vector<int> > levelOrder(TreeNode *root) {
          vector<vector<int>> result;
          traverse(root, 1, result);
          return result;
}
      void traverse(TreeNode *root, size_t level, vector<vector<int>> &result) {
          if (!root) return;
          if (level > result.size())
              result.push_back(vector<int>());
          result[level-1].push_back(root->val);
          traverse(root->left, level+1, result);
          traverse(root->right, level+1, result);
} };

Reference

• TREE层遍历