欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

107. Binary Tree Level Order Traversal II(二叉树广度遍历,自底向上输出)

程序员文章站 2022-05-18 19:39:15
...

problems:
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]
]
tip:
广度遍历使用队列实现,vector的反转实现自底向上输出。
solution:
迭代法:

 class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int>> res;
            queue<TreeNode *> q{{root}};
            while(!q.empty())
            {
                vector<int> vec;
                for(int i=q.size();i>0;i--)
                {
                    TreeNode *t=q.front();
                    q.pop();
                    vec.push_back(t->val);
                    if(t->left) q.push(t->left);
                    if(t->right) q.push(t->right);
                }
                res.push_back(vec);
            }
            reverse(res.begin(),res.end());//reverse()实现vector反转
            return res;
        }
    };

**递归法:**引入变量level来标记当前深度,即层数,

class Solution {
public:
   
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
       vector<vector<int>> res;
       dfs(root,0,res);
       reverse(res.begin(),res.end());
       return res;
    }
    void dfs(TreeNode *root,int level,vector<vector<int>>& res)//这里注意是vector的引用
    {
        if(!root) return;
        if(res.size() == level) res.push_back({});//当level等于向量大小时申请新的一层
        res[level].push_back(root->val);
        if(root->left) dfs(root->left,level+1,res);
        if(root->left) dfs(root->right,level+1,res);
    } 
};
相关标签: tree