没有递归解决不了的二叉树问题

Leetcode上的前120道题的简单题已经几乎做完了，递归数据类型的题还是遇到不少。递归是一种比较优雅的解题方法，奈何我并不能每次都很顺利地写出递归解法，所以在这里做一个Leetcode前120道简单题之二叉树问题递归解法总结。

---

100.相同的数

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

/**定义二叉树类，后同，省略

* 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) {
        //结束标志：两个树均为空
        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.对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

class Solution {
    //结束标志：根节点为空，或者根节点的只有左子树或右子树
    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);
        
    }
    //对称的情况：左右叶子节点均为空；左右叶子节点的值相同（则将子节点的左右子树作为输入再次迭代）
    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.二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

class Solution {
    public int maxDepth(TreeNode root) {
        //结束标志：根节点为空
        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.将有序数组转化成二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例：

给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

class Solution {
    //结束标志：待转化的数组为空
    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;
        }
        //找到数组中点作为根节点
        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);
        //返回根节点
        return root;
    }
}

---

110.平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。

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;
        }
    }
     
   //结束标志：根节点为空 
    public ReturnNode isBST(TreeNode root) {
        if(root == null) {
            return new ReturnNode(true, 0);
        }
         
        //不平衡的三种情况：左数不平衡， 右数不平衡 ，左右树深度差值大于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.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

class Solution {
    public int minDepth(TreeNode root) {
        //结束标志：根节点为空
        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;
    }
}

---

小结：其实递归解法的代码是有一定的规律的，主要需要注意三个地方：

• 递归结束的标志
• 单层递归中需要做的事情
• 每层递归给下一层传的返回值。

---

更新：好久没做，又有点忘了怎么写递归的程序了，补充一道2019/10/23做的题。
226.翻转二叉树
翻转一棵二叉树。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        //结束标识：节点为空
        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;
    }
}