首页 > 代码库 > Binary Tree Level Order Traversal II <leetcode>

Binary Tree Level Order Traversal II <leetcode>

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,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]

思路:本来想到用分支限界,但是代码写的很复杂,没有控制住,后来在网上看到一个方法,很简单,直接遍历,有些代码挺巧妙的,代码如下:

 

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10  struct node11  {12      TreeNode *val;13      int dep;14  };15 class Solution {16 public:17     vector<vector<int>>  result;18     vector<int>  temp;19     vector<vector<int> > levelOrderBottom(TreeNode *root) {20         doit(root,0);21         reverse(result.begin(),result.end());22         return result;23     }24     25     void doit(TreeNode *root,int level)26     {27         if(root==NULL)  return;28         else29         {30             if(level==result.size())31             {32                  vector<int> v;33                  result.push_back(v);34             }35             result[level].push_back(root->val);36             doit(root->left,level+1);37             doit(root->right,level+1);38         }39     }40 };

 

Binary Tree Level Order Traversal II <leetcode>