当前位置:网站首页>[leetcode] notes on recursive time value transfer and reference transfer

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

2022-06-11 01:54:00 xiaoshijiu333

#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

原网站

版权声明
本文为[xiaoshijiu333]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/03/202203020623173624.html