[LeetCode] Path Sum III 二叉树的路径和之三

阳光穿透心脏的1/2处 2022-04-14 04:55 126阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70][]

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
    
          10
         /  \
        5   -3
       / \    \
      3   2   11
     / \   \
    3  -2   1
    
    Return 3. The paths that sum to 8 are:
    
    1.  5 -> 3
    2.  5 -> 2 -> 1
    3. -3 -> 11

public class liubobo_7_5 {
        /// 437. Path Sum III
    /// https://leetcode.com/problems/path-sum-iii/description/
    /// 时间复杂度: O(n), n为树的节点个数
    /// 空间复杂度: O(h), h为树的高度
            /// Definition for a binary tree node.
            public static class TreeNode {
                int val;
                TreeNode left;
                TreeNode right;
                TreeNode(int x) { val = x; }
            }
    
            // 在以root为根节点的二叉树中,寻找和为sum的路径,返回这样的路径个数
            public int pathSum(TreeNode root, int sum) {
    
                if(root == null)
                    return 0;
    
                return findPath(root, sum)
                        + pathSum(root.left , sum)
                        + pathSum(root.right , sum);
            }
    
            // 在以node为根节点的二叉树中,寻找包含node的路径,和为sum
            // 返回这样的路径个数
            private int findPath(TreeNode node, int num){
    
                if(node == null)
                    return 0;
    
                int res = 0;
                if(node.val == num)
                    res += 1;
    
                res += findPath(node.left , num - node.val);
                res += findPath(node.right , num - node.val);
    
                return res;
            }
    
            public static void main(String[] args) {
    
                // 手动创建Leetcode题页上的测试用例。
                // 当然, 有更好的更智能的创建二叉树的方式, 有兴趣的同学可以自行研究编写程序:)
    
                /*****************
                 * 测试用例:
                 *
                 *       10
                 *      /  \
                 *     5   -3
                 *    / \    \
                 *   3   2   11
                 *  / \   \
                 * 3  -2   1
                 *****************/
                TreeNode node1 = new TreeNode(3);
                TreeNode node2 = new TreeNode(-2);
    
                TreeNode node3 = new TreeNode(3);
                node3.left = node1;
                node3.right = node2;
    
                TreeNode node4 = new TreeNode(1);
                TreeNode node5 = new TreeNode(2);
                node5.right = node4;
    
                TreeNode node6 = new TreeNode(5);
                node6.left = node3;
                node6.right = node5;
    
                TreeNode node7 = new TreeNode(11);
                TreeNode node8 = new TreeNode(-3);
                node8.right = node7;
    
                TreeNode node9 = new TreeNode(10);
                node9.left = node6;
                node9.right = node8;
    
                System.out.println((new liubobo_7_5()).pathSum(node9, 8));
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70]: /images/20220414/1aca9dd89150448e936db97b8d00d901.png