递归解题核心思想

1、递归要考虑的三个问题：

• 递归应该在什么时候结束？

• 我应该返回什么信息给上层？

• 在这一次的递归中，要完成什么任务？

递归每一层的功能都是一样的，所以只要解决了这三个问题，递归的问题就解决了

2、举例说明：

2.1、二叉树的最大深度

1、什么时候结束递归？

当遍历到树的左右节点都为空的时候，递归就结束了！

2、返回给上层的是什么？

因为是对树深度的遍历，所以返回给上层的，自然是这颗子树的深度

3、本次递归中，要完成什么任务？

每一次的递归，都是在获取树的深度，可能左右子树都存在，那么自然要返回最高的那颗树的值，同时，要加上1，因为本身的这棵树，也属于一层，当遍历到自身为null的时候，就返回0(不用+1)

4、代码如下：

public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return left > right ? left + 1 : right + 1;
    }

2.2、两两交换链表中的节点

问题描述：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

1、什么时候结束递归？

当已经到了最后的元素，不能再交换了，结束递归

2、返回给上层的是什么？

交换后的链表，把两个链表进行交换后，返回给上一层

3、本次递归中，要完成什么任务？

递归值考虑一层，也就意味着，我们眼中的一条链表，分成了三个部分

head-->head.next-->已经处理好的链表部分，我们要做的，自然就是把head和head.next进行交换

4、代码实现

        if (head == null || head.next == null) {
            return head;
        }
        /**
         * 用temp做中间临时变量
         */
        ListNode temp = head.next;
        //把排序好的链表，挂到head节点的next上面
        head.next = swapPairs(temp.next);
        //把head，挂到临时变量的next上面
        temp.next = head;
        return temp;

2.3、判断二叉树是否高度平衡

1、什么时候结束递归？

当左子树或右子树不为平衡二叉树时，或遍历完所有节点

2、返回给上层的是什么？

本层的子树，是否是一颗平衡二叉树

3、本次递归中，要完成什么任务？

计算本层的高度差，并判断本层的左子树和右子树是否是一个平衡二叉树

4、代码实现

 /**
     * 遍历左右子树的同时，计算左右子树的是否是个平衡二叉树
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }else {
            //返回当前树的高度差是否小于等于1
           return (Math.abs(maxHeight(root.left) - maxHeight(root.right)) <= 1)
                   //判断左子树和右子树，是否都是平衡的二叉树
                   && isBalanced(root.left) && isBalanced(root.right) ;
        }
    }
    //求树深度
    int maxHeight(TreeNode root){
        return root == null ? 0 : Math.max(maxHeight(root.left),maxHeight(root.right)) + 1;
    }

本文参考lyl大佬的博客，发表自己的意见，感谢lyl大佬提供的思路！