欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode437.路径总和III

程序员文章站 2022-06-06 20:40:03
...

LeetCode437.路径总和III
我的做法O(N^2)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root == null){
            return 0;
        }
        pathofcount(root,sum);
        //System.out.println("who:"+root.val+"|count: "+count);
        pathSum(root.left,sum);
        pathSum(root.right,sum);
        return count;
    }
    int count = 0;
    public void pathofcount(TreeNode root, int sum) {
        if(root == null){
            return;
        }
        sum -= root.val;
        if(sum == 0){
            count++;
        }
        pathofcount(root.left,sum);
        pathofcount(root.right,sum);
    }
}

别人的做法O(nlogn),从节点向上遍历求sum

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 class Solution{
     public int pathSum(TreeNode root, int sum) {
        return pathSum(root, sum, new int[1000], 0);
         }

    public int pathSum(TreeNode root, int sum, int[] array/*保存路径*/, int p/*指向路径终点*/)      {
        if (root == null) {
            return 0;
        }
        int tmp = root.val;
        int n = root.val == sum ? 1 : 0;
        for (int i = p - 1; i >= 0; i--) {
            tmp += array[i];
            if (tmp == sum) {
                n++;
            }
        }
        array[p] = root.val;
        int n1 = pathSum(root.left, sum, array, p + 1);
        int n2 = pathSum(root.right, sum, array, p + 1);
        return n + n1 + n2;
    }
 }