2015年6月30日星期二

LeetCode: Binary Tree Level Order Traversal II

Almost same with Binary Tree Level Order Traversal
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

没有评论:

发表评论