For example:
Given binary tree
{3,9,20,#,#,15,7}
,3 / \ 9 20 / \ 15 7return its bottom-up level order traversal as:
[ [15,7] [9,20], [3], ]
Solution: the basic idea is similar to Binary Tree Level Order Traversal I. [Another good solution: 1]
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int> > levelOrderBottom(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function if(root==NULL){ vector<vector<int> > ret; return ret; } vector<vector<int> > left, right; left = levelOrderBottom(root->left); right = levelOrderBottom(root->right); reverse(left.begin(), left.end()); reverse(right.begin(), right.end()); int numLayer = min(left.size(), right.size()); for(int i=0; i<numLayer; i++){ left[i].insert(left[i].end(), right[i].begin(), right[i].end()); } if(left.size()<right.size()){ left.insert(left.end(), right.begin()+numLayer, right.end()); } left.insert(left.begin(), vector<int>(1, root->val)); reverse(left.begin(), left.end()); return left; } };
No comments:
Post a Comment