剑指 Offer 34. 二叉树中和为某一值的路径

解题思路：回溯

如给定二叉树，以及目标和 target = 22

  1.               5
  2.              / \
  3.             4   8
  4.            /   / \
  5.           11  13  4
  6.          /  \    / \
  7.         7    2  5   1

题目要求我们返回所有路径和为 target 的序列：

[ [5,4,11,2] , [5,8,4,5] ]

本题是一道典型的二叉树搜索问题，使用回溯算法解决

算法流程：

递归函数：pathSum(TreeNode root,int target,int sum,List> res,List list)

返回值：void

参数解释：

  • TreeNode root ：遍历到的当前节点
  • int target ：题目给定的目标和
  • int sum ：遍历到当前节点的路径和
  • List> res ：题目要求的返回列表
  • List list ：添加到 res 结果集中符合条件的列表

递归终止条件：当节点为空，直接返回

递推过程：

  • 路径和的更新：sum = sum + root.val
  • list 添加至 res 条件：
    • root 为叶节点(左右节点均为 null)
    • sum = target
  • 遍历过程：先序遍历，先从根开始，递归左/右 子节点
  • 路径恢复：向上回溯前，需要移除当前的节点，即执行 list.removeLast()

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<List<Integer>> pathSum(TreeNode root, int target) {
  18.         List<List<Integer>> res = new LinkedList<>();
  19.         List<Integer> list = new LinkedList<>();
  20.         pathSum(root,target,0,res,list);
  21.         return res;
  22.     }
  24.     private static void pathSum(TreeNode root,int target,int sum,List<List<Integer>> res,List<Integer> list){
  25.         if(root == null){
  26.             return;
  27.         }
  28.         list.add(root.val);
  29.         sum += root.val;
  30.         if(root.left == null && root.right == null && sum == target){
  31.             res.add(new LinkedList<>(list));
  32.         }else {
  33.             pathSum(root.left,target,sum,res,list);
  34.             pathSum(root.right,target,sum,res,list);
  35.         }
  36.         list.remove(list.size() - 1);
  37.     }
  38. }

复杂度分析

  • 时间复杂度：O(N)

先序遍历需要遍历二叉树的所有节点

  • 空间复杂度：O(N)

最差的情况下，二叉树退化为链表，递归深度为 N，使用额外空间复杂度为 ： O(N)