leetcode 107 Binary Tree Level Order Traversal II(最底层往上依次输出二叉树每一个node的val)

2017-02-20 · 1 min read · 算法竞赛

最近要准备面试…虽然leetcode的题目难度比较水..不过白板写代码还是要练下的。。。我所理解的白板写代码。。。大概就是。。。用记事本。。一遍写对代码的能力吧。。。所以我来记录一下。。思路想错的或者没有秒的题目。

（因为题目描述傻逼/数据范围故意坑人/leetcode抽风 / 我自己犯傻逼 等原因 没有一次通过的题目不在记录之列）

leetcode107

题意：给一棵二叉树，从最底层往上依次输出每一个node的val..

思路：一开始以为同一层的一定会在相邻时间内访问。。。后来发现的确是蠢了。。。

因此dfs的时候加了一个level域。。。每次dfs的时候先左后右就好了。。。

注意记得判断root为空的情况。。。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年02月20日 星期一 19时21分51秒
 4File Name :107.cpp
 5************************************************ */
 6/**
 7
 8 * Definition for a binary tree node.
 9
10 * struct TreeNode {
11
12 *     int val;
13
14 *     TreeNode *left;
15
16 *     TreeNode *right;
17
18 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
19
20 * };
21
22 */
23
24class Solution {
25
26public:
27
28    vector<vector<int>>res;
29    vector<int>tmp[1500];
30    int mx_level = 0 ;
31    void dfs( TreeNode* root,int level)
32    {
33//  cout<<"level:"<<level<<endl;
34    mx_level = max(mx_level,level);
35    if (root->left!=NULL)
36    {
37        tmp[level].push_back(root->left->val);
38        dfs(root->left,level+1);
39    }
40    if (root->right!=NULL)
41    {
42        tmp[level].push_back(root->right->val);
43        dfs(root->right,level+1);
44    }
45    }
46    vector<vector<int>> levelOrderBottom(TreeNode* root) {
47    if (root==NULL) return res; 
48        tmp[0].push_back(root->val);
49        dfs(root,1);
50        for ( int i = mx_level;  i>= 0 ; i--)if (!tmp[i].empty()) res.push_back(tmp[i]);
51    return res;
52    }
53
54};