题目如下:
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
给定一棵二叉树和一个整数sum,让我们找出所有从根节点到叶子节点权值之和为sum的路径。
解题思路为,对二叉树进行深度优先搜索(DFS),并记录所走过的路径,到达叶子节点时判断路径和与sum是否相等,若相等则将路径添加到结果中。
实现代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { if (root == null) { return new LinkedList<>(); } List res = new LinkedList<>(); dfs(res, root, sum, new LinkedList<Integer>()); return res; } private void dfs(List res, TreeNode root, int sum, List<Integer> list) { if (root.left == null && root.right == null) { if (root.val == sum) { list.add(root.val); res.add(new LinkedList<>(list)); list.remove(list.size() - 1); } return; } list.add(root.val); if (root.left != null) { dfs(res, root.left, sum - root.val, list); } if (root.right != null) { dfs(res, root.right, sum - root.val, list); } list.remove(list.size() - 1); return; } }
二叉树每个节点访问一次,时间复杂度为O(n)。
- 本文固定链接: https://weiguangli.com/archives/406
- 转载请注明: lwg0452 于 Weiguang的博客 发表
捐 赠如果您觉得这篇文章有用处,请支持作者!鼓励作者写出更好更多的文章!