[LeetCode107 ] Binary Tree Level Order Traversal II 二叉树层序遍历之二

Category	Difficulty	Likes	Dislikes
algorithms	Easy (65.56%)	257	-

TagsCompanies

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

返回其自底向上的层次遍历为：

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

方法一：
本题是102 的简单变形，代码如下：

 1 /*
 2  * @Descripttion: 
 3  * @version: 
 4  * @Author: wangxf
 5  * @Date: 2020-07-07 23:09:12
 6  * @LastEditors: Do not edit
 7  * @LastEditTime: 2020-07-07 23:10:30
 8  */ 
 9 /*
10  * @lc app=leetcode.cn id=107 lang=cpp
11  *
12  * [107] 二叉树的层次遍历 II
13  */
14 
15 // @lc code=start
16 /**
17  * Definition for a binary tree node.
18  * struct TreeNode {
19  *     int val;
20  *     TreeNode *left;
21  *     TreeNode *right;
22  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
23  * };
24  */
25 struct NodeInfo
26 {
27     TreeNode* ptr = nullptr;
28     int level = 0;
29     NodeInfo(TreeNode* node_ptr,int node_level):
30     ptr(node_ptr),level(node_level)
31     {}
32 };
33 class Solution {
34 public:
35     vector<vector<int>> levelOrderBottom(TreeNode* root)
36     {
37         std::vector<vector<int>> res;
38         if(!root) return res;
39         std::queue<NodeInfo> q;
40         NodeInfo root_node(root,0);
41         q.push(root_node);
42         while(!q.empty())
43         {
44             NodeInfo cur_node = q.front();
45             q.pop();
46             int cur_level = cur_node.level;
47             int cur_node_val = cur_node.ptr->val;
48             if(res.size()<cur_level+1)
49             {
50                 vector<int> tempVec;
51                 res.push_back(tempVec);
52             }
53             res[cur_level].push_back(cur_node_val);
54             if(cur_node.ptr->left)
55             {
56                NodeInfo leftNode(cur_node.ptr->left,cur_level+1);
57                q.push(leftNode);
58             }
59             if(cur_node.ptr->right)
60             {
61                NodeInfo rightNode(cur_node.ptr->right,cur_level+1);
62                q.push(rightNode);
63             }
64         }
65         std::reverse(res.begin(),res.end());
66         return res;
67 
68     }
69 };
70 // @lc code=end