Leetcode上的前120道題的簡單題已經(jīng)幾乎做完了，遞歸數(shù)據(jù)類型的題還是遇到不少。遞歸是一種比較優(yōu)雅的解題方法，奈何我并不能每次都很順利地寫出遞歸解法，所以在這里做一個(gè)Leetcode前120道簡單題之二叉樹問題遞歸解法總結(jié)。

100.相同的數(shù)

給定兩個(gè)二叉樹，編寫一個(gè)函數(shù)來檢驗(yàn)它們是否相同。

如果兩個(gè)樹在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。

/**定義二叉樹類，后同，省略

* Definition for a binary tree node.

* public class TreeNode {

*    int val;

*    TreeNode left;

*    TreeNode right;

*    TreeNode(int x) { val = x; }

* }

*/

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //結(jié)束標(biāo)志：兩個(gè)樹均為空
        if(p == null && q == null){
            return true;
        }
        //兩樹均不為空且值相同
        if(p != null && q != null && p.val == q.val){
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }else{
            return false;
        }
    }
}

101.對(duì)稱二叉樹
給定一個(gè)二叉樹，檢查它是否是鏡像對(duì)稱的。
例如，二叉樹 [1,2,2,3,4,4,3] 是對(duì)稱的。

class Solution {
    //結(jié)束標(biāo)志：根節(jié)點(diǎn)為空，或者根節(jié)點(diǎn)的只有左子樹或右子樹
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        if((root.left == null && root.right != null)||(root.left != null && root.right == null)){
            return false;
        }
        return isSymmetricChild(root.left, root.right);
        
    }
    //對(duì)稱的情況：左右葉子節(jié)點(diǎn)均為空；左右葉子節(jié)點(diǎn)的值相同（則將子節(jié)點(diǎn)的左右子樹作為輸入再次迭代）
    private boolean isSymmetricChild(TreeNode left, TreeNode right){
        if(left == null && right == null){
            return true;
        }
        if((left == null && right != null)||(right == null && left != null)){
            return false;
        }
        if(left.val == right.val){
            return isSymmetricChild(left.left,right.right) && isSymmetricChild(right.left,left.right);
        }
        else{
            return false;
        }
    }
}

104.二叉樹的最大深度
給定一個(gè)二叉樹，找出其最大深度。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。

class Solution {
    public int maxDepth(TreeNode root) {
        //結(jié)束標(biāo)志：根節(jié)點(diǎn)為空
        if(root == null){
            return 0;
        };
        //左右子樹的最大深度，+1
        int left = maxDepth(root.left) + 1;
        int right = maxDepth(root.right) + 1;
        int max = Math.max(left, right);
        //返回子樹最大深度的最大值
        return max;
    }
}

108.將有序數(shù)組轉(zhuǎn)化成二叉搜索樹
將一個(gè)按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹。
本題中，一個(gè)高度平衡二叉樹是指一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1。
示例：

給定有序數(shù)組: [-10,-3,0,5,9],
一個(gè)可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個(gè)高度平衡二叉搜索樹：

class Solution {
    //結(jié)束標(biāo)志：待轉(zhuǎn)化的數(shù)組為空
    public TreeNode sortedArrayToBST(int[] nums) {
        return nums == null ? null : buildTree(nums, 0, nums.length - 1);
    }
    
    private TreeNode buildTree(int[] nums, int l , int r){
        if(l > r){
            return null;
        }
        //找到數(shù)組中點(diǎn)作為根節(jié)點(diǎn)
        int m = l + (r - l) / 2;
        TreeNode root = new TreeNode(nums[m]);
        //左右子樹分別建立二叉樹
        root.left = buildTree(nums, l , m - 1);
        root.right = buildTree(nums, m + 1, r);
        //返回根節(jié)點(diǎn)
        return root;
    }
}

110.平衡二叉樹
給定一個(gè)二叉樹，判斷它是否是高度平衡的二叉樹。

class Solution {
    
    public boolean isBalanced(TreeNode root) {
        return isBST(root).isB;
    }
    
    private class ReturnNode {
        boolean isB;
        int depth;
        public ReturnNode(boolean isB, int depth){
            this.isB = isB;
            this.depth = depth;
        }
    }
     
   //結(jié)束標(biāo)志：根節(jié)點(diǎn)為空 
    public ReturnNode isBST(TreeNode root) {
        if(root == null) {
            return new ReturnNode(true, 0);
        }
         
        //不平衡的三種情況：左數(shù)不平衡， 右數(shù)不平衡 ，左右樹深度差值大于1
        ReturnNode left = isBST(root.left);
        ReturnNode right = isBST(root.right);
        if(left.isB == false || right.isB == false) {
            return new ReturnNode(false, 0);
        }
        if(Math.abs(left.depth - right.depth) > 1) {
            return new ReturnNode(false, 0);
        }
        //返回左右子樹的最大深度，+1
        return new ReturnNode(true, Math.max(left.depth, right.depth) + 1);
    }
}

111.二叉樹的最小深度
給定一個(gè)二叉樹，找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

class Solution {
    public int minDepth(TreeNode root) {
        //結(jié)束標(biāo)志：根節(jié)點(diǎn)為空
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        //左右子樹的最小深度，+1
        int a = minDepth(root.left) + 1;
        a = (a==1 ? Integer.MAX_VALUE : a);
        int b = minDepth(root.right) + 1;
        b = (b==1 ? Integer.MAX_VALUE : b);
        int min = Math.min(a, b);//
        //返回子樹中的最小深度
        return min;
    }
}

小結(jié)：其實(shí)遞歸解法的代碼是有一定的規(guī)律的，主要需要注意三個(gè)地方：

• 遞歸結(jié)束的標(biāo)志
• 單層遞歸中需要做的事情
• 每層遞歸給下一層傳的返回值。

更新：好久沒做，又有點(diǎn)忘了怎么寫遞歸的程序了，補(bǔ)充一道2019/10/23做的題。
226.翻轉(zhuǎn)二叉樹
翻轉(zhuǎn)一棵二叉樹。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        //結(jié)束標(biāo)識(shí)：節(jié)點(diǎn)為空
        if (root == null) {
            return root;
        } else {
            //交換操作
            TreeNode node = root.right;
            root.right = root.left;
            root.left = node;
            
            root.right = invertTree(root.right);
            root.left = invertTree(root.left);
        }
        return root;
    }
}