Could anyone please tell me where is wrong with my code?


  • 0
    B

    I was trying to use level order traversal & greedy to solve this problem, calculate the sum of the node values in the even levels of the tree and the sum of the node values in the odd levels of the tree, then return the maximum of these two number.

    But I can't pass the test, could anyone please give me some hints about where goes wrong? Thank you so much!

    public int rob(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        int odd_level = 0;
        int even_level = 0;
        boolean flag = true;
        
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        
        while(! q.isEmpty()){
            int num_of_level = q.size();
            for(int i = 0; i < num_of_level; i ++){
                if(q.peek().left != null){
                    q.add(q.peek().left);
                }
                if(q.peek().right != null){
                    q.add(q.peek().right);
                }
                if(flag){
                    odd_level += q.poll().val;
                }else{
                    even_level += q.poll().val;
                }
            }
            if(flag){
                flag = false;
            }else{
                flag = true;
            }
        }
        
        return odd_level > even_level ? odd_level : even_level;
    }

  • 3
    W

    I think your solution ignore the situations that like 4,1,null,2,null,3, the best solution is 4 + 3 = 7, however, if you calculate level by level your answer will be 4 + 2 = 6, this is because you ignore the fact that you can actually skip more than one level to get the answer. You rob the first level doesnt mean you have to rob the third level. Hope i can make this clear.


  • 1
    C

    Another example could be [3,8,5,1,3,null,10] where answer is 8+10 = 18 where constituent elements forming the solution lie in the consecutive levels. It is also worthwhile to note that solution would not necessarily include all the elements on same level.


  • 0
    B

    Thank you for your explanation! I got it!


  • 0
    B

    Thanks for your example, I got it!


Log in to reply
 

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