Using DFS and TreeMap, really want to know what's wrong here


  • 0
    T
    public class Solution {
         public static List<List<Integer>> verticalOrder(TreeNode root) {
    	        List<List<Integer>> res=new ArrayList<List<Integer>>();
    	        if(root==null)
    	          return res;
    	        TreeMap<Integer,List<Integer>> map1=new TreeMap<Integer,List<Integer>>();
    	        dfs(root,0,map1);
    	       for(List<Integer> list:map1.values()){
    	    	   res.add(list);
    	       }
    	        return res;
    	    }
    	    public static  void dfs(TreeNode root,int index,TreeMap<Integer,List<Integer>> map1){
    	        if(root==null)
    	          return;
    	        if(!map1.containsKey(index)){
    	           map1.put(index,new ArrayList<Integer>());
    	        }
    	        map1.get(index).add(root.val);
    	        dfs(root.left,index-1,map1);
    	        dfs(root.right,index+1,map1);
    	    }
    }
    

    Really don't know what's wrong with my code and how to solve it. Please help me.
    ![alt text](0_1474745713984_Capture.PNG image url)


  • 0
    D

    I've got the same answer when I tried DFS.

    So the problem requires you to output the node's value in a "level-order" sort of sequence.

    If you write that tree out, you would find that "8" is the right child of root and is supposed to come out first.


  • 0
    T

    so, do you think we can still solve the problem using DFS? Thanks!


  • 0
    S

    @tracymcgrady Just simply pass in the level of the tree. Every time when you add the value to the dictionary, add the value with the level. Then sort values by level in increasing order for each group in the dictionary. That's it.


  • 0
    S

    I also ran into an issue when I did a DFS traversal. Then I switched to a BFS (level by level) approach and that solved my problem.
    Notice that if you do DFS, 2 comes first while if you do BFS 8 is the one that is processed first.


  • 0
    T

    @hamster ok, thanks


  • 0

    It's kind of forcing you to do BFS, since val in the same col must maintain level order as well.. you need to swap 8 and 2.


  • 0

    @Samuri @tracymcgrady Actually, only adding tree level accompany with the node value is not enough to resolve "collision" (as shown in Example 2 & 3 in the problem when multiple nodes could be in the same group with the same level).

    Another indicator to resolve "collision" order is actually by pre-order traversal sequence, i.e., the ealier node in pre-order traversal will always comes first in result if such "collision" happens.

    I have a version DFS similar to yours with pre-order traversal index recorded:

        typedef map<pair<int,int>, int> P2I;
        map<int, P2I> tmp;
        int pi = 0; // pre-order index
        
        vector<vector<int>> verticalOrder(TreeNode* r) {
            preOrder(r);
            vector<vector<int>> res;
            auto second = [](P2I::value_type itr) { return itr.second; };
            for (auto& col : tmp) {
                res.push_back({});
                transform( col.second.begin(), col.second.end(), back_inserter( res.back() ), second );
            }
            return res;        
        }
        
        // vi: vertical index; li: level index
        void preOrder(TreeNode* r, int vi = 0, int li = 0) {
            if (!r) return;
            tmp[vi].emplace(make_pair(li, pi++), r->val);
            preOrder(r->left,  vi-1, li+1);
            preOrder(r->right, vi+1, li+1);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.