I used the standard DFS solution:
It can be easily realized based on tree methods in my previous article: http://codinggamestart.blogspot.com/2015/06/leetcode-binary-tree-level-order.html
for BFS with queue: change result.push_back(v) to result.insert(result.begin(), v);
for BFS with two queues: same with above;
for DFS the tricky solution: way 1 is to change it to standard solution like below
way 2 is to change push_back to insert, and notice the index change, become not straightforward.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | /** * Definition for a binary tree node. * 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) { int height=getHeight(root); vector<vector<int>> result(height); if(height==0) return result; preorder(root,height-1,result); return result; } int getHeight(TreeNode* node){ int left=1; int right=1; if(node==NULL) return 0; if(node->left!=NULL) left+=getHeight(node->left); if(node->right!=NULL) right+=getHeight(node->right); return (left>right)?left:right; } void preorder(TreeNode* node, int n, vector<vector<int>>& result){ if(node==NULL) return; result[n].push_back(node->val); if(node->left!=NULL) preorder(node->left, n-1, result); if(node->right!=NULL) preorder(node->right, n-1, result); } }; |
Reference: http://siddontang.gitbooks.io/leetcode-solution/content/tree/binary_tree_level_order_traversal.html
没有评论:
发表评论