剑指offer-38-串字符串的排列（套路解决递归算法问题）

落日映苍穹つ 2021-12-07 13:45 139阅读 0赞

[套路解决递归算法问题][Link 1]

例1：求二叉树的最大深度  
先看一道简单的Leetcode题目： Leetcode 104. 二叉树的最大深度  
题目很简单，求二叉树的最大深度，那么直接套递归解题三部曲模版：

找终止条件。什么情况下递归结束？当然是树为空的时候，此时树的深度为0，递归就结束了。

找返回值。应该返回什么？题目求的是树的最大深度，我们需要从每一级得到的信息自然是当前这一级对应的树的最大深度，因此我们的返回值应该是当前树的最大深度，这一步可以结合第三步来看。

本级递归应该做什么。首先，还是强调要走出之前的思维误区，递归后我们眼里的树一定是这个样子的，看下图。此时就三个节点：root、root.left、root.right，其中根据第二步，root.left和root.right分别记录的是root的左右子树的最大深度。那么本级递归应该做什么就很明确了，自然就是在root的左右子树中选择较大的一个，再加上1就是以root为根的子树的最大深度了，然后再返回这个深度即可。  
链接：[https://www.jianshu.com/p/1395fae8a1ae][https_www.jianshu.com_p_1395fae8a1ae]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]  
解题思路  
　　①如果一棵树只有一个结点，它的深度为1。

②如果根结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1；同样如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1。

③如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加1。

比如在上图的二叉树中，根结点为1的树有左右两个子树，其左右子树的根结点分别为结点2和1。根结点为2的左子树的深度为2，而根结点为3的右子树的深度为1，因此根结点为1的树的深度就是3。

package offer.Leetcode;
    
    
    import org.junit.Test;
    
    /**
     * 求二叉树的最大深度
     * @author kankan
     * @creater 2019-07-17 8:57
     */
    public class Solution1 {
        public int maxDepth(TreeNode root){
            //1.找终止条件：树为空时结束递归，并返回当前深度0
            if (null == root){
                return 0;
            }
            //2.本级递归：找到root的左右子树的最大深度
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            //3.找返回值：左右子树的最大深度+1
            return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
        }
        @Test
        public void testDepth01(){
            TreeNode root=new TreeNode(1);
            TreeNode left1=new TreeNode(2);
            TreeNode left2=new TreeNode(3);
            TreeNode right1=new TreeNode(4);
            //创建一棵树
            //             1
            //         /      \
            //        2        4
            //         \
            //         3
            root.left=left1;
            left1.right=left2;
            root.right=right1;
            System.out.println(new Solution1().maxDepth(root));
        }
    }

![在这里插入图片描述][20190717143204748.png]  
例2：两两交换链表中的节点  
看了一道递归套路解决二叉树的问题后，有点套路搞定递归的感觉了吗？我们再来看一道Leetcode中等难度的链表的问题，掌握套路后这种中等难度的问题真的就是秒：Leetcode 24. 两两交换链表中的节点  
直接上三部曲模版：

找终止条件。什么情况下递归终止？没得交换的时候，递归就终止了呗。因此当链表只剩一个节点或者没有节点的时候，自然递归就终止了。

找返回值。我们希望向上一级递归返回什么信息？由于我们的目的是两两交换链表中相邻的节点，因此自然希望交换给上一级递归的是已经完成交换处理，即已经处理好的链表。

本级递归应该做什么。结合第二步，看下图！由于只考虑本级递归，所以这个链表在我们眼里其实也就三个节点：head、head.next、已处理完的链表部分。而本级递归的任务也就是交换这3个节点中的前两个节点，就很easy了。

package offer.Leetcode;
    
    import org.junit.Test;
    
    /**
     * @author kankan
     * @creater 2019-07-17 14:38
     */
    public class Solution2 {
        public ListNode swapPairs(ListNode head){
            //1.终止条件：链表只有一个节点或者没有节点了，没得交换。返回的是已经处理好的链表
            if (null == head || null == head.next){
                return head;
            }
            //2.本级递归应该做什么
            //一共三个节点：head，next,swapPairs(next.next)
            ListNode next = head.next;
            head.next = swapPairs(next.next);//返回上一级交换出来结果，已经处理好的链表
            next.next = head;
            //根据第二步：返回给上一级的事当前已经完成交换后，即处理好了的链表部分
            return next;
        }
        @Test
        public void testDepth01(){
            ListNode root=new ListNode(1);
            ListNode listNode1=new ListNode(2);
            ListNode listNode2=new ListNode(3);
            ListNode lisNode3=new ListNode(4);
            root.next = listNode1;
            listNode1.next = listNode2;
            listNode2.next = lisNode3;
            ListNode listNode = new Solution2().swapPairs(root);
            while (listNode != null){
                System.out.println(listNode.data);
                listNode = listNode.next;
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 1]  
例3：平衡二叉树  
Leetcode 110. 平衡二叉树

package offer.Leetcode;
    
    import org.junit.Test;
    
    /**
     * Leetcode 110. 平衡二叉树
     * @author kankan
     * @creater 2019-07-17 21:01
     */
    public class Solution3 {
        public boolean isBalanced(TreeNode root){
            return isBST(root).isB;
        }
        //参考递归套路的第三部：描述单次执行过程是什么样的
        //这里的单次执行过程具体如下：
        //是否终止?->没终止的话，判断是否满足不平衡的三个条件->返回值
        public ReturnNode isBST(TreeNode root) {
            if (null == root){
                return new ReturnNode(0,true);
            }
            //不平衡的情况有3种：左树不平衡、右树不平衡、左树和右树差的绝对值大于1
            ReturnNode left = isBST(root.left);
            ReturnNode right = isBST(root.right);
            if (false == left.isB || false == right.isB){
                return new ReturnNode(0,false);
            }
            if (Math.abs(left.depth -  right.depth) > 1){
                return new ReturnNode(0,false);
            }
            //不满足上面3种情况，说明平衡了，树的深度为左右俩子树最大深度+1
            return new ReturnNode(Math.max(left.depth, right.depth) + 1, true);
        }
        @Test
        public void testDepth01(){
            TreeNode root=new TreeNode(1);
            TreeNode left1=new TreeNode(2);
            TreeNode left2=new TreeNode(3);
            TreeNode right1=new TreeNode(4);
            //创建一棵树
            //             1
            //         /      \
            //        2        4
            //         \
            //         3
            root.left=left1;
            left1.right=left2;
            root.right=right1;
            System.out.println(new Solution3().isBalanced(root));
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 2]

package offer;
    
    import java.util.ArrayList;
    import java.util.Collections;
    
    /**
     *题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，
      则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
     * @author kankan
     * @creater 2019-07-14 8:38
     */
    public class Solution38 {
        public ArrayList<String> permutation(String str){
            ArrayList<String> list = new ArrayList<>();
            if (null == str || 0 == str.length()){
                return list;
            }
            permutationCore(str.toCharArray(),0,list);
            Collections.sort(list);//将list中的字符串排序
            return list;
        }
    
        private void permutationCore(char[] chars, int index, ArrayList<String> list) {
            if (index == chars.length - 1){
                if (!list.contains(String.valueOf(chars))){//判断是否有重复的字符串
                    list.add(String.valueOf(chars));
                }
            }else {
                for (int i = index;i < chars.length;i++){
                    //1.求出所有可能出现在第一个位置的字符
                    char temp = chars[index];
                    chars[index] = chars[i];
                    chars[i] = temp;
                    //2.固定第一个字符，求后面字符的排列
                    permutationCore(chars,index+1,list);
                    //还原成abc
                    chars[i] = chars[index];
                    chars[index] = temp;
                }
            }
        }
    
        public static void main(String[] args) {
            String str = "abc";
            ArrayList<String> permutation = new Solution38().permutation(str);
            System.out.println(permutation);
        }
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 3]

[Link 1]: https://www.jianshu.com/p/1395fae8a1ae?tdsourcetag=s_pctim_aiomsg
[https_www.jianshu.com_p_1395fae8a1ae]: https://www.jianshu.com/p/1395fae8a1ae
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]: /images/20211207/014927560e7f4539b85ce93cdb78c678.png
[20190717143204748.png]: /images/20211207/5e93bb9bc76a448f8be1c27abd1df479.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 1]: /images/20211207/246bf9fef10b4655b707250ff4c29d48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 2]: /images/20211207/7e4c4b606c0b4103b59ef0dac13d3057.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 3]: /images/20211207/b650fce7736d466abfad9c2e595f2ba0.png