【回溯专题】剑指 Offer 34. 二叉树中和为某一值的路径

共以下 4 个回答

• 行动派小彩笔 普通 2023年9月18日 下午8:48

   // dfs的思想
  class Solution {
  public:
      vector<vector<int>> ans;
      vector<int> path;
      void dfs(TreeNode* node,int target)
      {
          if(node==nullptr) return;
          path.push_back(node->val);
          target-=node->val;
          if(target==0&&node->left ==nullptr&&node->right == nullptr) ans.push_back(path);
          dfs(node->left,target);
          dfs(node->right,target);
          path.pop_back();
      } 
      vector<vector<int>> pathSum(TreeNode* root, int target) {
          dfs(root,target);
          return ans;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 小肸 永久会员 2023年9月17日 上午10:34

  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  class Solution {
      static List<List<Integer>> res;
      public List<List<Integer>> pathSum(TreeNode root, int target) {
          res = new ArrayList<>();
          dfs(root, target, 0, new LinkedList<>());
          return res;
      }
      //深搜，递归+回溯
      private void dfs(TreeNode node, int target, int currentSum, LinkedList<Integer> tmp) {
          if (node == null) {
              return;
          }
          if (node.left == null && node.right == null && currentSum + node.val == target) {
              tmp.add(node.val);
              res.add(new LinkedList<>(tmp));
              tmp.removeLast();
              return;
          }
          tmp.add(node.val);
          dfs(node.left, target, currentSum + node.val, tmp);
          dfs(node.right, target, currentSum + node.val, tmp);
          tmp.removeLast();
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• sincere 普通 2023年9月14日 下午6:16

  • 思路：前序遍历，满足条件就把path数组加到list中，不满足就回溯
  • 复杂度：时间复杂度O(n), 空间复杂度O(n)

  class Solution {
      List<List<Integer>> list = new ArrayList<>();
      // 用LinkedList保证加入顺序 可以向上回溯
      LinkedList<Integer> path = new LinkedList<>();
  
      public List<List<Integer>> pathSum(TreeNode root, int target) {
          dfs(root, target);
          return list;
      }
  
      void dfs(TreeNode root, int target) {
          if (root == null) {
              return;
          }
          path.add(root.val);
          target -= root.val;
          // 路径和相等且当前节点为叶子节点
          if (target == 0 && root.left == null && root.right == null) {
              list.add(new LinkedList<>(path));//避免加入引用
          } else {
              dfs(root.left, target);
              dfs(root.right, target);
          }
          path.removeLast();// 不满足就回溯，删除当前节点
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年9月9日 下午5:18

  暴力dfs
  时间复杂度O(n), 空间复杂度O(n)

  class Solution {
      private List<Integer> temp = new ArrayList<>();
      private List<List<Integer>> list = new ArrayList<>();
      private int target;
      public List<List<Integer>> pathSum(TreeNode root, int target) {
          this.target = target;
          if (root == null) {
              return list;
          }
          dfs(root, 0);
          return list;
      }
  
      public void dfs(TreeNode root, int sum) {
          if (root == null) {
              return ;
          }
          temp.add(root.val);
          // 为叶节点
          if (root.left == null && root.right == null) {
              if (root.val + sum != target) {
                  temp.remove(temp.size() - 1);
                  return ;
              }
              list.add(temp.stream().collect(Collectors.toList()));
          }
          dfs(root.left, root.val + sum);
          dfs(root.right, root.val + sum);
  
          temp.remove(temp.size() - 1);
      }
  }
  

  0 赞同 0 条回复

  登录以回复