[leetcode] notes on recursive time value transfer and reference transfer

#LeetCode A daily topic 【 Special topic of binary tree 】

• stay java The basic types in are value passing , Instead of basic types, they are passed by reference ; When it is used as a parameter in the recursive process , Pay attention to branch pollution , And whether it is necessary to go back

• int Pass as a parameter

  because int It's worth passing on , Every time a method is called recursively, a value is passed in , After recursive call , It does not affect the original value , That is, there is no branch pollution problem

  Such as ：LeetCode104 Find the sum of numbers from root node to leaf node

  	int ans = 0;
  
      public int sumNumbers(TreeNode root) {
        
          getSum(root, 0);
          return ans;
      }
  
      private void getSum(TreeNode root, int sum) {
        
          if (root == null) return;
          sum = sum * 10 + root.val;
          if (root.left == null && root.right == null) {
        
              ans+=sum;
          }
          getSum(root.left, sum);
          getSum(root.right, sum);
      }
  

• String Pass as a parameter

  String Itself is passed by reference , But he is special ,String yes final Of , Every time + Or the assignment actually generates a new String object , That is, there is no branch pollution problem in the recursive process , No backtracking operation is required ;

  With the above int Different ： If there is an operation , Each recursive call generates a new String Into

  Such as ：LeetCode257 All paths of binary tree

  public List<String> binaryTreePaths(TreeNode root) {
        
          List<String> ans = new ArrayList<>();
          binaryTreePaths2(root, "", ans);
          return ans;
      }
  
      // string Adding is too slow 
      //  Just want to explain , Use it directly String Why not go back , Because use String Of + A new object has been generated by 
      //  The next time a value is passed recursively, a new object is passed in 
      private void binaryTreePaths(TreeNode root, String res, List<String> ans) {
        
          if (root == null) return;
          if (res.length() == 0) {
        
              res += root.val;
          } else {
        
              res = res + "->" + root.val;
          }
          if (root.left == null && root.right == null) {
        
              ans.add(res);
          }
          binaryTreePaths(root.left, res, ans);
          binaryTreePaths(root.right, res, ans);
      }
  

• List Pass in as a parameter

  list Is the easiest point to make mistakes , Sometimes it is easy to overlook the fact that list After being passed in as a parameter , Then make corresponding modifications , This of the original method list The changes have been synchronized without realizing .

  The same is true in recursion , When calling this method recursively list Made modifications , That goes back to the original when using the list The modification will be kept synchronously , That is, branch pollution in recursion , Scenarios that require backtracking

  Such as ：LeetCode113 The sum of the paths II

  List<List<Integer>> ans = new LinkedList<>();
  
      public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        
          LinkedList<Integer> res = new LinkedList<>();
          pathSum(root, targetSum, res);
          return ans;
      }
  
      //  Depth-first search + to flash back 
      private void pathSum(TreeNode root, int targetSum, LinkedList<Integer> res) {
        
          if (root == null) return;
          res.add(root.val);
          if (root.left == null && root.right == null) {
        
              //  The leaf node satisfies the final condition 
              if (root.val == targetSum) {
        
                  //  want new A collection goes in , Otherwise, it will be synchronously modified later 
                  ans.add(new LinkedList<>(res));
              }
          }
          pathSum(root.left, targetSum - root.val, res);
          pathSum(root.right, targetSum - root.val, res);
          //  Go back , Remove the current node from the collection 
          res.pollLast();
      }
  

  If you don't want to go back , Be similar to String That kind of , A new... Can be generated at each recursive call list Pass in , So every time the operation is called list They don't affect each other （ But there are collections copy A lot of time and space overhead ）

  //  Depth-first search + Each recursion generates a new set , Guaranteed not to interfere with other recursive branches 
      private void pathSum2(TreeNode root, int targetSum, LinkedList<Integer> res) {
        
          if (root == null) return;
          //  Every time the recursion comes in, it will re new A collection , This ensures that the parameters res Does not interfere with each other in each recursion , There is no need to go back 
          LinkedList<Integer> temp = new LinkedList<>(res);
          temp.add(root.val);
          if (root.left == null && root.right == null) {
        
              if (root.val == targetSum) {
        
                  ans.add(temp);
              }
          }
          pathSum2(root.left, targetSum - root.val, temp);
          pathSum2(root.right, targetSum - root.val, temp);
      }
  

• summary

  In the recursive process, we can quickly identify whether there will be branch pollution problem , Whether backtracking operation is required , Pay special attention to List The situation of