Leetcode 107. Binary Tree Level Order Traversal II(python+cpp)

题目

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree [3,9,20,null,null,15,7],

解法1：DFS

class Solution:def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:def helper(root,level):if root:if len(ans)<=level: ans.insert(0,[])ans[-(level+1)].append(root.val)helper(root.left,level+1)helper(root.right,level+1)ans = []helper(root,0)return ans

时间复杂度：O(N)
空间复杂度：O(N)

解法2：BFS

class Solution:def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:class Solution:def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:if not root:return []ans = []q = collections.deque()q.append(root)while q:ans.insert(0,[])n = len(q)for i in range(n):node = q.popleft()ans[0].append(node.val)if node.left:q.append(node.left)if node.right:q.append(node.right)return ans

时间复杂度：O(N)
空间复杂度：O(N)

C++版本BFS：

class Solution {
    
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {
    queue<TreeNode*> q;vector<int> ans;vector<vector<int>>res;if(root == NULL){
    return res;}q.push(root);while(!q.empty()){
    int currentSize = q.size();for(int i = 0; i < currentSize; i++){
    TreeNode* temp = q.front();q.pop();if(temp){
    ans.push_back(temp->val);if(temp->left) q.push(temp->left);if(temp->right) q.push(temp->right);}}res.push_back(ans);ans.clear();}// reverse the array reverse(res.begin(), res.end());return res;}
};