能力随心，自然成长

0%

路径总和问题

发表于 更新于 分类于

关于leetcode中路径总和的几道题目的整理。

路径总和I

  • leetcode112

  • 题目描述： 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

  • 解题思路：递归，sum值每次递归减去其根结点的值

  • java代码：

    1
    class Solution {
    2
        public boolean hasPathSum(TreeNode root, int sum) {
    3
            if (root == null)
    4
                return false;
    5
            sum -= root.val; 
    6
            if (root.left == null && root.right == null) {
    7
                return sum == 0;
    8
            }
    9
            return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    10
        }
    11
    }

路径总和II

  • leetcode113，剑指offer34

  • 题目描述： 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

  • 解题思路：递归，利用一个数组保存遍历的路径，如果遇到根结点并且满足条件则输出。

  • java代码：

    1
    class Solution {
    2
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
    3
            List<List<Integer>> ans = new ArrayList<>();
    4
            List<Integer> arry = new ArrayList<>();
    5
            dfs(root, sum, arry, ans);
    6
            return ans;
    7
        }
    8
    9
        public void dfs(TreeNode root, int sum, List<Integer> arry, List<List<Integer>> ans) {
    10
            if (root == null) return;
    11
            arry.add(root.val);
    12
            sum -= root.val;
    13
            if (root.left == null && root.right == null && sum == 0) {
    14
                //ans.add(arry); //整个递归过程用的是同一个arry，需要把当前的状态保存下来，否则最后的输出全为空[]
    15
                ans.add(new ArrayList<>(arry));
    16
            }
    17
            dfs(root.left, sum, arry, ans);
    18
            dfs(root.right, sum, arry, ans);
    19
            arry.remove(arry.size() - 1);//回溯，去除当前的根结点，继续寻找下一个满足条件的路径
    20
        }
    21
    }

路径总和III

  • leetcode437

  • 题目描述：给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。

    路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

  • 解题思路：

    • 思路1：递归，从每一个节点出发，找到所有满足条件的路径，两层递归。
    • 思路2：考虑到每个节点到根节点的路径是唯一的。用一维数组保存当前节点到根节点的所有路径，用一个标记表示当前路径的终点。

  • java代码：

    1
    class Solution {
    2
        //思路1 双重递归
    3
        //先序遍历每一个结点，在以每一个节点作为起始节点递归查找
    4
        private int num = 0;
    5
        public int pathSum(TreeNode root, int sum) {
    6
            if (root == null) return 0;
    7
            cal_sum(root, sum);
    8
            pathSum(root.left, sum);
    9
            pathSum(root.right, sum);
    10
            return num;
    11
        }
    12
        //计算当前结点作为根结点的所有满足的路径
    13
        public void cal_sum(TreeNode root, int sum) {
    14
            if (root == null) return;
    15
            sum -= root.val;
    16
            if (sum == 0) {
    17
                num++;
    18
            }
    19
            cal_sum(root.left, sum);
    20
            cal_sum(root.right, sum);
    21
        }
    22
    }
    1
    class Solution {
    2
       //思路2
    3
        /**核心：每个节点到根节点的路径是唯一的
    4
        * 1.用一维数组保存当前节点到根节点的所有路径
    5
        * 2.用一个标记表示当前路径的终点
    6
        * 3.先序遍历所有节点
    7
        */
    8
        public int pathSum(TreeNode root, int sum) {
    9
            return cal_sum(root, sum, new int[1000], 0);
    10
        }
    11
        //arry数组用于保存遍历过的路径
    12
        public int cal_sum(TreeNode root, int sum, int arry[], int p) {
    13
            if (root == null) return 0;
    14
            int n = (root.val == sum ? 1 : 0); //判断单独的节点是否满足条件
    15
            int cur = root.val; 
    16
            for (int i = p - 1; i >= 0; i--) { //根结点出发到当前结点的所有可能值
    17
                cur += arry[i];
    18
                if (cur == sum) {
    19
                    n++;
    20
                }
    21
            }
    22
            arry[p] = root.val; //访问过的结点加入数组
    23
            int n1 = cal_sum_2(root.left, sum, arry, p + 1);
    24
            int n2 = cal_sum_2(root.right, sum, arry, p + 1);
    25
            return n + n1 + n2;
    26
        }
    27
    }