[leetcode]: 107. Binary Tree Level Order Traversal II

r囧r小猫 2022-06-15 03:51 130阅读 0赞

# 1.题目 #

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\],

3
    / \
    9  20
    /  \
    15  7

return its bottom-up level order traversal as:  
\[\[15,7\],\[9,20\],\[3\]\]  
二叉树按层来遍历，自底向上

# 2.分析 #

BFS：广度优先遍历，用vector存每层遍历的结果。最后reverse  
DFS：深度优先遍历，需要加额外参数level来标记当前元素在哪一层。

# 3.代码 #

BFS

class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int>> ans;
            if (root == NULL)
                return ans;
            //广度优先用queue，深度优先用stack
            queue<TreeNode*> nodes;
            nodes.push(root);
            while (!nodes.empty()) {
                int num = nodes.size();
                vector<int> level;
                for (int i = 0; i < num; i++) {
                    TreeNode* tmp = nodes.front();
                    nodes.pop();
                    level.push_back(tmp->val);
                    if (tmp->left != NULL)
                        nodes.push(tmp->left);
                    if (tmp->right != NULL)
                        nodes.push(tmp->right);         
                }
                ans.push_back(level);
            }
            reverse(ans.begin(),ans.end());
            return ans;
        }
    };

DFS

class Solution {
    public:
        void DFS(vector<vector<int>>& ans,TreeNode* root, int level) {
            if (root == NULL)
                return;
            if (level >= ans.size())
                ans.push_back(vector<int>());
            ans[level].push_back(root->val);
            DFS(ans, root->left, level + 1);
            DFS(ans, root->right, level + 1);
        }
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int>> ans;
            if (root == NULL)
                return ans;
            DFS(ans, root, 0);
            reverse(ans.begin(), ans.end());
            return ans;
        }
    };