102. 二叉树的层序遍历(Binary Tree Level Order Traversal)M

英文题目

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,null,null,15,7],

return its level order traversal as:
```
[
  [3],
  [9,20],
  [15,7]
]
```

中文题目

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],

返回其层次遍历结果：
```
[
  [3],
  [9,20],
  [15,7]
]
```

迭代

使用队列，存储每一层的左右子节点，然后逐个出队遍历即可

时间复杂度O(n)，空间复杂度O(n)

# python3: 时间 44 ms, 击败 61.1%; 内存 16.7 MB, 击败 48.60%
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root:
            return res
        q = deque([root])
        while q:
            size = len(q)
            levelList = []
            for _ in range(size):
                node = q.popleft()
                levelList.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(levelList)
        return res

// c++: 时间 4 ms, 击败 78.72%; 内存 13.1 MB, 击败 46%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr) {
            return res;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            vector<int> levelList;
            for (int i = 0; i < size; ++i) {
                TreeNode * node = q.front();
                q.pop();
                levelList.push_back(node->val);
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            res.push_back(levelList);
        }
        return res;
    }
};

// java: 时间 1 ms, 击败 84.23%; 内存 43 MB, 击败 14.6%
/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> levelList = new ArrayList<>();
            for (int i = 0; i < size; ++i) {
                TreeNode node = q.peek();
                q.poll();
                levelList.add(node.val);
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
            res.add(levelList);
        }
        return res;
    }
}

// go: 时间 0 ms, 击败 100%; 内存 3.4 MB, 击败 54.37%
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }
    q := []*TreeNode{root}
    for len(q) > 0 {
        size := len(q)
        levelList := []int{}
        for i := 0; i < size; i++ {
            node := q[0]
            q = q[1:]
            levelList = append(levelList, node.Val)
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
        res = append(res, levelList)
    }
    return res
}

// javascript: 时间 64 ms, 击败 86.27%; 内存 44.5 MB, 击败 15.69%
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    const res = [];
    if (!root) {
        return res;
    }
    const q = [root];
    while (q.length) {
        const size = q.length;
        const levelList = [];
        for (let i = 0; i < size; ++i) {
            const node = q.shift();
            levelList.push(node.val);
            if (node.left) {
                q.push(node.left);
            }
            if (node.right) {
                q.push(node.right);
            }
        }
        res.push(levelList);
    }
    return res;
};

递归

相当于前序遍历，在参数上维护一个level，标识当前是在哪一层

时间复杂度O(n)，空间复杂度O(n)

# python3: 时间 44 ms, 击败 61.1%; 内存 18.7 MB, 击败 5.4%
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        self.res = []
        self.dfs(root, 0)
        return self.res
    
    def dfs(self, root: Optional[TreeNode], level: int) -> None:
        if not root:
            return
        if len(self.res) <= level:
            self.res.append([])
        self.res[level].append(root.val)
        self.dfs(root.left, level+1)
        self.dfs(root.right, level+1)

// c++: 时间 4 ms, 击败 78.72%; 内存 14.2 MB, 击败 5%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        dfs(res, root, 0);
        return res;
    }

    void dfs(vector<vector<int>>& res, TreeNode* root, int level) {
        if (root == nullptr) {
            return;
        }
        if (res.size() <= level) {
            res.push_back(vector<int>());
        }
        res[level].push_back(root->val);
        dfs(res, root->left, level+1);
        dfs(res, root->right, level+1);
    }
};

// java: 时间 1 ms, 击败 84.23%; 内存 43 MB, 击败 10.30%
/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, root, 0);
        return res;
    }

    private void dfs(List<List<Integer>> res, TreeNode root, int level) {
        if (root == null) {
            return;
        }
        if (res.size() <= level) {
            res.add(new ArrayList<>());
        }
        res.get(level).add(root.val);
        dfs(res, root.left, level+1);
        dfs(res, root.right, level+1);
    }
}

// go: 时间 0 ms, 击败 100%; 内存 3.8 MB, 击败 7.31%
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    dfs(&res, root, 0)
    return res
}

func dfs(res *[][]int, root *TreeNode, level int) {
    if root == nil {
        return
    }
    if len(*res) <= level {
        *res = append(*res, []int{})
    }
    (*res)[level] = append((*res)[level], root.Val)
    dfs(res, root.Left, level+1)
    dfs(res, root.Right, level+1)
}

// javascript: 时间 80 ms, 击败 26.37%; 内存 44.4 MB, 击败 27.49%
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    const res = [];
    dfs(res, root, 0);
    return res;
};

const dfs = function(res, root, level) {
    if (root == null) {
        return;
    }
    if (res.length <= level) {
        res.push([]);
    }
    res[level].push(root.val);
    dfs(res, root.left, level+1);
    dfs(res, root.right, level+1);
}

# 102. 二叉树的层序遍历(Binary Tree Level Order Traversal)M

# 英文题目

# 中文题目

# 迭代

# 递归

102. 二叉树的层序遍历(Binary Tree Level Order Traversal)M

英文题目

中文题目

迭代

递归