第六部分：深度优先搜索
104.二叉树的最大深度（简单）
题目：给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
输入：root = [1,null,2] 输出：2
第一种思路：
感觉递归的思路已经深入骨髓了，虽然使用不是非常流畅，但是慢慢有感觉了。
叶子节点检查：
首先检查当前节点的左右子节点是否都为
null。如果是，说明当前节点是叶子节点，返回1，表示深度为1。单子节点检查：
如果右子节点为
null，则递归调用maxDepth计算左子树的深度，并在结果上加1。如果左子节点为
null，则递归调用maxDepth计算右子树的深度，并在结果上加1。递归深度计算：
如果左右子节点都存在，函数会分别调用
maxDepth计算左右子树的深度，并返回1加上两个深度中的最大值。但是仅仅到这里就会出现空指针异常（测试后才发现，属于是粗心了）
按上面思路的代码漏了root为NULL的情况，代码如下：
class Solution {public int maxDepth(TreeNode root) {//一开始漏了这种情况：if(root==null) return 0;if(root.left==null && root.right==null) return 1;else if(root.right==null) return 1 + maxDepth(root.left);else if(root.left==null) return 1 + maxDepth(root.right);else return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));} }在加上root==null的情况后，代码也就可以简化了。
整体思路：
基本情况：
首先检查
root是否为null。如果是，说明树是空的，返回0，表示深度为0。递归调用：
如果当前节点不为空，函数会递归调用
maxDepth方法来计算左子树和右子树的深度。
maxDepth(root.left)计算左子树的深度，maxDepth(root.right)计算右子树的深度。深度计算：
使用
Math.max函数来获取左子树和右子树深度中的最大值。最后，返回
1 +最大深度，1表示当前节点的深度。
/*** Definition for a binary tree node.* 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) { // 如果当前节点为空，返回深度为0 if (root == null) { return 0; } // 递归计算左子树和右子树的深度，取最大值并加1（当前节点） return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }
}100.相同的树（简单）
题目：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3] 输出：true
示例 2：
输入：p = [1,2], q = [1,null,2] 输出：false
第一种思路：
相同的树？很容易想到的是直接将树中的值读出来然后一一比较，唯一的问题是，当某一节点有右子树而没有左子树时，可能会产生错误，所以可以将这一NULL值用某一特定值代替，然后注意到，这两棵树节点值：
-104 <= Node.val <= 104，所以我就设置为了10001。
isSameTree 方法:
该方法用于判断两棵二叉树是否相同。
首先调用
valueOfTree方法获取两棵树的节点值列表list1和list2。计算两棵树中较长的列表长度
leng。遍历较长的列表，逐个比较对应位置的值。如果发现任何一个位置的值不相等，立即返回
false。如果所有值都相等，返回
true。valueOfTree 方法:
该方法用于将二叉树的节点值存储到列表中。
如果当前节点为空，添加一个特殊值（
10001）表示空节点。如果当前节点不为空，首先添加当前节点的值，然后递归调用自身以添加左子树和右子树的节点值。
/*** Definition for a binary tree node.* 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 isSameTree(TreeNode p, TreeNode q) {// 获取两棵树的节点值列表List<Integer> list1 = valueOfTree(p);List<Integer> list2 = valueOfTree(q);// 取两棵树中较长的列表长度int leng = Math.max(list1.size(), list2.size());// 遍历较长的列表，比较对应位置的值for (int i = 0; i < leng; i++) {// 如果某个位置的值不相等，返回 falseif (!list1.get(i).equals(list2.get(i))) {return false;}}// 如果所有值都相等，返回 truereturn true;}// 将二叉树的节点值存储到列表中public List<Integer> valueOfTree(TreeNode root) {List<Integer> list = new ArrayList<>();// 如果当前节点为空，添加一个特殊值（10001）表示空节点if (root == null) {list.add(10001);return list;}// 添加当前节点的值list.add(root.val);// 递归添加左子树和右子树的节点值list.addAll(valueOfTree(root.left));list.addAll(valueOfTree(root.right));return list;}
}该实现的时间复杂度为 O(n)，其中 n 是树中节点的数量，因为每个节点都被访问一次。空间复杂度也是 O(n)，用于存储节点值的列表。
第二种思路：
基准情况:
如果两个节点都为空（
p == null && q == null），则返回true，表示这部分树是相同的。如果一个节点为空而另一个节点不为空（
p == null || q == null），则返回false，表示这部分树不同。如果两个节点的值不相等（
p.val != q.val），则返回false，表示这部分树不同。递归情况:
如果以上条件都不满足，说明当前节点的值相等，接下来递归比较左子树和右子树。
使用逻辑与（
&&）运算符，只有当左子树和右子树都相同时，才返回true。
/*** Definition for a binary tree node.* 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 isSameTree(TreeNode p, TreeNode q) { // 如果两个节点都为空，返回 true（两棵树相同） if (p == null && q == null) { return true; } // 如果一个节点为空，另一个节点不为空，返回 false（两棵树不同） else if (p == null || q == null) { return false; } // 如果两个节点的值不相等，返回 false（两棵树不同） else if (p.val != q.val) { return false; } // 递归比较左子树和右子树 else { return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } }
}