Ugly but easy to understand


  • 0
    class Solution {
        private int res;
        public int pathSum(int[] nums) {
            res=0;
            dfs(nums,0,0);
            return res;
        }
        private void dfs(int[] nums, int root, int path)
        {
            int left=getleft(nums,root);
            int right=getright(nums,root);
            
            if(left==-1 && right==-1)
            {
                path+=nums[root]%10;
                res+=path;
                return;
            }
            if(left!=-1)dfs(nums,left,path+nums[root]%10);
            if(right!=-1)dfs(nums,right,path+nums[root]%10);
        }
        private int getleft(int[] nums, int root)
        {
            int root_lvl=(nums[root]/100);
            int root_pos=(nums[root]%100)/10;
            
            for(int i=root+1;i<nums.length;i++)
            {
                if(root_lvl+1==nums[i]/100 && root_pos*2-1 == (nums[i]%100)/10)return i;
            }
            return -1;
        }
        private int getright(int[] nums, int root)
        {
            int root_lvl=(nums[root]/100);
            int root_pos=(nums[root]%100)/10;
            
            for(int i=root+1;i<nums.length;i++)
            {
                if(root_lvl+1==nums[i]/100 && root_pos*2 == (nums[i]%100)/10)return i;
            }
            return -1;
        }
    }
    

Log in to reply
 

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