面试算法大全-递归总结

秒速五厘米 2022-10-17 13:51 187阅读 0赞

## 8.递归 ##

### 8.1 递归算法总结 ###

构成递归需具备的条件:  
1 . 子问题须与原始问题为同样的事， 且更为简单；  
2 . 不能无限制地调用本身， 须有个出口， 化简为非递归状况处理。

直接或者间接调用自身的算法叫做**递归算法**。

### 8.2 经典题目源码总结 ###

#### [二叉搜索树的范围和][Link 1] ####

方法一：深度优先搜索

class Solution {
        
        int ans;
        public int rangeSumBST(TreeNode root, int L, int R) {
        
            ans = 0;
            dfs(root, L, R);
            return ans;
        }
        public void dfs(TreeNode node, int L, int R) {
        
            if (node != null) {
        
                if (L <= node.val && node.val <= R)
                    ans += node.val;
                if (L < node.val)
                    dfs(node.left, L, R);
                if (node.val < R)
                    dfs(node.right, L, R);
            }
        }
    }

迭代实现深度优先搜索

class Solution {
        
        public int rangeSumBST(TreeNode root, int L, int R) {
        
            int ans = 0;
            Stack<TreeNode> stack = new Stack();
            stack.push(root);
            while (!stack.isEmpty()) {
        
                TreeNode node = stack.pop();
                if (node != null) {
        
                    if (L <= node.val && node.val <= R)
                        ans += node.val;
                    if (L < node.val)
                        stack.push(node.left);
                    if (node.val < R)
                        stack.push(node.right);
                }
            }
            return ans;
        }
    }

#### [二叉树的坡度][Link 2] ####

方法：递归

public class Solution {
        
        int tilt=0;
        public int findTilt(TreeNode root) {
        
            traverse(root);
            return tilt;
        }
        public int traverse(TreeNode root)
        {
        
            if(root==null ){
        
                return 0;
            }
            int left=traverse(root.left);
            int right=traverse(root.right);
            tilt+=Math.abs(left-right);
            return left+right+root.val;
        }
    }

#### [青蛙跳台阶问题][Link 3] ####

public static int f(int n) {
        
            if (n <= 1)
                return 1;
            if (n < 3)
                return n;
            return f(n - 1) + f(n - 2);
        }

#### [重建二叉树][Link 4] ####

方法一：递归

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            if (preorder == null || preorder.length == 0) {
        
                return null;
            }
            Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
            int length = preorder.length;
            for (int i = 0; i < length; i++) {
        
                indexMap.put(inorder[i], i);
            }
            TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
            return root;
        }
    
        public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
        
            if (preorderStart > preorderEnd) {
        
                return null;
            }
            int rootVal = preorder[preorderStart];
            TreeNode root = new TreeNode(rootVal);
            if (preorderStart == preorderEnd) {
        
                return root;
            } else {
        
                int rootIndex = indexMap.get(rootVal);
                int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;
                TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
                TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
                root.left = leftSubtree;
                root.right = rightSubtree;
                return root;
            }
        }
    }

方法二：迭代

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            if (preorder == null || preorder.length == 0) {
        
                return null;
            }
            TreeNode root = new TreeNode(preorder[0]);
            int length = preorder.length;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            int inorderIndex = 0;
            for (int i = 1; i < length; i++) {
        
                int preorderVal = preorder[i];
                TreeNode node = stack.peek();
                if (node.val != inorder[inorderIndex]) {
        
                    node.left = new TreeNode(preorderVal);
                    stack.push(node.left);
                } else {
        
                    while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
        
                        node = stack.pop();
                        inorderIndex++;
                    }
                    node.right = new TreeNode(preorderVal);
                    stack.push(node.right);
                }
            }
            return root;
        }
    }

#### [最长同值路径][Link 5] ####

class Solution {
        
        int ans;
        public int longestUnivaluePath(TreeNode root) {
        
            ans = 0;
            longestPath(root);
            return ans;
        }
        //递归函数功能：搜寻以node为起点的最长同值路径:要么是以node为起点的左子树，要么是以node为起点的右子树
        public int longestPath(TreeNode node) {
        
            if (node == null) return 0;
            int maxLorRres=0;
            int left = longestPath(node.left); //node左子树的最长同值路径
            int right = longestPath(node.right);//node右子树的最长同值路径
            //这种情况对于寻找最长同值路径长有帮助，对于搜索以root为路径起始点的最长路径没有帮助
            if (node.left != null && node.left.val == node.val&&node.right != null && node.right.val == node.val) {
        
                ans=Math.max(ans, left + right+2);
            }
            //从左右子树中选择最长的同值路径
            if(node.left!=null&&node.left.val == node.val){
        
                maxLorRres=left+1;
            }
            if(node.right!=null&&node.right.val==node.val){
        
                maxLorRres=Math.max(maxLorRres,right+1);
            }
            //从ans与maxLorRres中更新最大值
            ans=Math.max(ans,maxLorRres);
            return maxLorRres; //所以你能知道为什么返回这个值了吗？
        }
    
    }

#### [递归乘法][Link 6] ####

class Solution {
        
        public int multiply(int A, int B) {
        
            if (A==1) return B;
            if (B==1) return A;
            
            if (A>B) return A + multiply(A, --B);
            
                return B+multiply(--A,B);
    
        }
    }

#### [二叉搜索树节点最小距离][Link 7] ####

方法一：排序【通过】

class Solution {
        
        List<Integer> vals;
        public int minDiffInBST(TreeNode root) {
        
            vals = new ArrayList();
            dfs(root);
            Collections.sort(vals);
    
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < vals.size() - 1; ++i)
                ans = Math.min(ans, vals.get(i+1) - vals.get(i));
    
            return ans;
        }
    
        public void dfs(TreeNode node) {
        
            if (node == null) return;
            vals.add(node.val);
            dfs(node.left);
            dfs(node.right);
        }
    }

方法二：中序遍历【通过】

class Solution {
        
        Integer prev, ans;
        public int minDiffInBST(TreeNode root) {
        
            prev = null;
            ans = Integer.MAX_VALUE;
            dfs(root);
            return ans;
        }
    
        public void dfs(TreeNode node) {
        
            if (node == null) return;
            dfs(node.left);
            if (prev != null)
                ans = Math.min(ans, node.val - prev);
            prev = node.val;
            dfs(node.right);
        }
    }

#### [汉诺塔问题][Link 8] ####

class Solution {
        
        /**
         * 将 A 上的所有盘子，借助 B，移动到C 上
         * @param A 原柱子
         * @param B 辅助柱子
         * @param C 目标柱子
         */
        public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        
            movePlate(A.size(), A, B, C);
        }
    
        private void movePlate(int num, List<Integer> original, List<Integer> auxiliary, List<Integer> target) {
        
            if (num == 1) {
            // 只剩一个盘子时，直接移动即可
                target.add(original.remove(original.size() - 1));
                return;
            }
    
            movePlate(num - 1, original, target, auxiliary);   // 将 size-1 个盘子，从 original 移动到 auxiliary
            target.add(original.remove(original.size() - 1));   // 将 第size个盘子，从 original 移动到 target
            movePlate(num - 1, auxiliary, original, target);   // 将 size-1 个盘子，从 auxiliary 移动到 target
        }
    }

[Link 1]: https://leetcode-cn.com/problems/range-sum-of-bst/
[Link 2]: https://leetcode-cn.com/problems/binary-tree-tilt/
[Link 3]: https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
[Link 4]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
[Link 5]: https://leetcode-cn.com/problems/longest-univalue-path/
[Link 6]: https://leetcode-cn.com/problems/recursive-mulitply-lcci/
[Link 7]: https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
[Link 8]: https://leetcode-cn.com/problems/hanota-lcci/