题目：二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

思路1：采用递归的方法，用maxDepth求出树的最大深度，再将最后结果+1

复杂度分析：时间复杂度O(N), 空间复杂度O(height)取决于树的最大深度

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight,rightHeight)+1;
        }
    }
}

也可以用三元运算符进行简化

return root ==null ? 0 : Math.max(maxDepth(root.left),maxDepth(root.right))+1;

思路2：迭代BFS,首先判断输入的结点是否存在，当不存在的时候直接返回0，当存在时，初始化队列，进入while循环

复杂度分析：时间复杂度O(N), 空间复杂度O(1)~O(N)

import java.util.LinkedList;
import java.util.Queue;
public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size-->0){
                TreeNode node = queue.poll();
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null){
                    queue.offer(node.right);
                }
            }
            res++;
        }
        return res;
    }
}

题目：恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

树上节点的数目在范围 [2, 1000] 内
-2^31 <= Node.val <= 2^31 - 1

思路1：显式中序遍历

import java.util.ArrayList;
import java.util.List;
public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
    public void recoverTree(TreeNode root) {
        List<Integer> nums = new ArrayList<Integer>();
        inorder(root,nums);
        int []swapped = findTwoSwapped(nums);
        recover(root,2,swapped[0],swapped[1]);
    }
    public void inorder(TreeNode root,List<Integer> nums){
        //递归,采用中序遍历将数值存入nums里面
        if (root == null){
            return;
        }
        inorder(root.left,nums);
        nums.add(root.val);
        inorder(root.right,nums);
    }
    public int [] findTwoSwapped(List<Integer> nums){
        int n = nums.size();
        int index1 = -1,index2 = -1;
        for (int i=0;i<n-1;i++){
            if (nums.get(i+1)<nums.get(i)){
                index2=i+1;
                if (index1 ==-1){
                    index1=i;
                }else{
                    break;
                }
            }
        }
        int x = nums.get(index1),y = nums.get(index2);
        return new int[]{x,y};
    }
    public void recover(TreeNode root,int count,int x,int y){
        if (root != null){
            if (root.val == x||root.val==y){
                root.val = root.val ==x?y:x;
                if (--count==0){
                    return;
                }
            }
            recover(root.right,count,x,y);
            recover(root.left,count,x,y);
        }
    }
}

题目：平衡二叉树

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

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：

输入：root = []
输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-10^4 <= Node.val <= 10^4

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        else{
            return Math.abs(height(root.left)- height(root.right))<=1 && isBalanced(root.left) &&isBalanced(root.right
            );
        }
    }
    public int height(TreeNode root){
        if (root ==null){return 0;}
        else{
            return Math.max(height(root.left),height(root.right))+1;
        }
    }
}