@TOC
# 前言 本文通篇基于TreeNode类进行解题，其代码如下，下面不再赘述： ```java 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; } } ```
# 一、二叉树的最大深度  ```java public int maxDepth(TreeNode root) { if(root==null){ return 0; } return search(root,1); } public int search(TreeNode root,int counter){ int n1 = counter,n2 = counter; if(root.left!=null){ n1 = search(root.left,counter+1); } if(root.right!=null){ n2 = search(root.right,counter+1); } return Math.max(n2, n1); } ```
# 二、验证二叉搜索树  ```java public boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean isValidBST(TreeNode root, long min, long max) { if (root == null){ return true; } //每个节点如果超过这个范围，直接返回false if (root.val >= max || root.val <= min){ return false; } //这里再分别以左右两个子节点分别判断， //左子树范围的最小值是min，最大值是当前节点的值，也就是root的值，因为左子树的值要比当前节点小 //右子数范围的最大值是max，最小值是当前节点的值，也就是root的值，因为右子树的值要比当前节点大 return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max); } ```
# 三、对称二叉树  ```java public boolean isSymmetric(TreeNode root) { if (root == null) return true; //从两个子节点开始判断 return search(root.left, root.right); } public boolean search(TreeNode left, TreeNode right) { //如果左右子节点都为空，说明当前节点是叶子节点，返回true if (left == null && right == null){ return true; } //如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false if (left == null || right == null || left.val != right.val){ return false; } //然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较 return search(left.left, right.right) && search(left.right, right.left); } ```
# 四、二叉树的层序遍历  ```java /** * 解题思路：深度优先搜索 */ public List> levelOrder(TreeNode root) { if(root==null){ return new ArrayList<>(); } List> reslut = new ArrayList<>(); // 将root节点值加入第一层 reslut.add(new ArrayList<>(List.of(root.val))); // 遍历子节点 return dfs(root.right,dfs(root.left,reslut,1),1); } public List> dfs(TreeNode cur,List> curList,int index){ if(cur==null){ // 如果当前节点为空，则直接返回 return curList; } if(index>=curList.size()){ // 说明没有遇到那么深的层数，向list中加层 curList.add(new ArrayList<>(List.of(cur.val))); }else{ // 说明遇到过那么深的层数，向list中获取该层，向其中加入当前节点值 curList.get(index).add(cur.val); } // 继续向子节点遍历 return dfs(cur.right,dfs(cur.left,curList,index+1),index+1); } ```
# 五、将有序数组转换为二叉搜索树  ```java // 题中说了要转换为一棵高度平衡的二叉搜索树，并且数组又是排过序的，我们可以使用递归的方式 //每次取数组中间的值比如 m作为当前节点，m前面的值作为他左子树的结点值，m后面的值作为他右子树的节点值 public TreeNode sortedArrayToBST(int[] num) { if (num.length == 0){ return null; } return search(num, 0, num.length - 1); } public TreeNode search(int[] num, int start, int end) { if (start > end){ return null; } int mid = (start + end) / 2; TreeNode root = new TreeNode(num[mid]); root.left = search(num, start, mid - 1); root.right = search(num, mid + 1, end); return root; } ```
