Friday, February 6, 2015

LeetCode [103] Binary Tree Zigzag Level Order Traversal

103. Binary Tree Zigzag Level Order Traversal
Medium

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]
 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * 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 {
    vector<vector<int>> ret;
    void helper(TreeNode* node, int level){
        if(node==NULL) return;
        if(ret.size()<level+1) ret.resize(level+1);
        ret[level].push_back(node->val);
        helper(node->left, level+1);
        helper(node->right, level+1);
    }
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        helper(root, 0);
        for(int i=0; i<ret.size(); ++i){
            if(i%2==1) reverse(ret[i].begin(), ret[i].end());
        }
        return ret;
    }
};

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        bfs(root, res, 1);
        return res;
    }
    void bfs(TreeNode* root, vector<vector<int>> &res, int level){
        if(!root) return;
        if(res.size()<level) res.resize(level);
        if(level%2==1){
            res[level-1].push_back(root->val);
        }else{
            res[level-1].insert(res[level-1].begin(), root->val);
        }
        bfs(root->left, res, level+1);
        bfs(root->right, res, level+1);
    }
};


 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
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> lists;
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        lists = new ArrayList<>();
        dfs(root, 0);
        return lists;
    }
    
    void dfs(TreeNode node, int level){
        if(node==null) return;
    //    System.out.println(node.val+" "+level);
        if(lists.size()==level){
            lists.add(new ArrayList<>());
        }
        List<Integer> last = lists.get(level);
        if(level%2==1)
            last.add(0, node.val);
        else
            last.add(node.val);
        dfs(node.left, level+1);
        dfs(node.right, level+1);
    }
}
Posted by at
Labels: , , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)