[Leet Code]Path Sum II

7961 단어 code
이 문제는 #1과 #4가 지점교환을 판단하면 대집합이 시간을 초과한다(비엽자 노드에 대해 매번 엽자 노드인지 아닌지를 판단해야 하기 때문이다).이를 통해 알 수 있듯이if else 판단 문장도 운행 시간에 비교적 큰 영향을 미칠 수 있다.
 
import java.util.ArrayList;



class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int currSum = 0;
    private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> tryPath = new ArrayList<Integer>();
    private ArrayList<Integer> oneSuccPath;
    
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        result.clear();
        tryPath.clear();
        
        if (null == root)
            return result;
        
        pathSumCore(root, sum);
        return result;
    }
    
    public void pathSumCore(TreeNode root, int sum) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (null == root)
            return;
        
        currSum += root.val;
        tryPath.add(root.val);

        // #1       
        if (null != root.left && null != root.right) {    
            pathSumCore(root.left, sum);
            pathSumCore(root.right, sum);
            currSum -= root.val;
            tryPath.remove(tryPath.size()-1);
            return;
        }
        // #2      
        else if (null == root.left && null != root.right) {
            pathSumCore(root.right, sum);
            currSum -= root.val;
            tryPath.remove(tryPath.size()-1);
            return;
        }
        // #3      
        else if (null == root.right && null != root.left) {
            pathSumCore(root.left, sum);
            currSum -= root.val;
            tryPath.remove(tryPath.size()-1);
            return;
        }
        // #4     
        else {//
            if (currSum == sum) {
                oneSuccPath = new ArrayList<Integer>(tryPath);
                result.add(oneSuccPath);
                currSum -= root.val;
                tryPath.remove(tryPath.size()-1);
                return;
            }
            else {
                currSum -= root.val;
                tryPath.remove(tryPath.size()-1);
                return;
            }
        }
    }
    
    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(-2);
        TreeNode c = new TreeNode(-3);
        TreeNode d = new TreeNode(1);
        TreeNode e = new TreeNode(3);
        TreeNode f = new TreeNode(-2);
        TreeNode g = new TreeNode(-1);

        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        d.left = g;

        Solution sl = new Solution();
        sl.pathSum(a, 2);
    }
}

좋은 웹페이지 즐겨찾기