My simple 2ms java solution - recursive


  • 2
    A
        public class Pair{
            int node;
            int child;
            public Pair(int node, int child){
                this.node = node;
                this.child = child;
            }
        }
        public int rob(TreeNode root) {
            Pair res = inorder(root);
            return res.node;
        }
        
        public Pair inorder(TreeNode root){
            if(root == null){
                return new Pair(0,0);
            }
            
            if(root.left == null && root.right == null){
                return new Pair(root.val, 0);
            }
            Pair left,right,node;
            left = right = node = null;
            if(root.left != null){
                left = inorder(root.left);
            }
            if(root.right != null){
                right = inorder(root.right);
            }
            
            int max_self = root.val;
            int max_child = 0;
            if(left != null){
                max_self += left.child;
                max_child += left.node;
            }
            if(right != null){
                max_self += right.child;
                max_child += right.node;
            }
            return new Pair( Math.max(max_self,max_child), max_child);
        }

  • 0
    T

    Why this one is so fast?

    I used 700 ms on my solution:

    public class Solution {
        public int rob(TreeNode root) {
            if(root==null) return 0;
            if(root.left==null&&root.right==null) return root.val;
            int rIn=root.val, rOut=0;
            if(root.left!=null){
                rIn+=(rob(root.left.left)+rob(root.left.right));
                rOut+=rob(root.left);
            }
            if(root.right!=null){
                rIn+=(rob(root.right.left)+rob(root.right.right));
                rOut+=rob(root.right);
            }
            return (rIn>rOut?rIn:rOut);
        }
    }

  • 0
    H

    What about the input [6,4,5,null,null,100,1]? It should be 6+100+1 = 107.
    Has this solution considered the situation of Maximum stored in deffrient level of the tree?


  • 0
    S

    Your solution takes more time as it repeats the rob function call for the nodes many times over.


Log in to reply
 

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