最小深度二叉树的最小深度是指从根节点到最近的叶子节点的最短路径上的节点数。叶子节点是指没有子节点的节点。所以如果某个子树为null则应该返回另一个子树里的最小深度比如不应该返回1而应该返回3因为根节点不是叶子节点所以不能返回1利用dfspublic static int minDepth(Node root) { if (root null) { return 0; } int count1 minDepth(root.left) 1; int count2 minDepth(root.right) 1; // 处理子树为null的情况 if (count1 0 || count2 0) { // 如果有一个子树为null则返回另一棵子树的深度 // 如果两棵树都为空只有根节点那么深度就是1就返回1 return 1 count1 count2; } return Math.min(count1, count2); }路径数字二叉树的节点填写0-9的数字每条根到叶子的路径能组成一个数字比如有一个路径为1-2-3则数字为123返回所有这些数字之和利用dfspublic static int t1(Node root,int num) { if (root null) { return 0; } // 递归出口走到叶子节点 if (root.left nullroot.right null) { // 如果num*10 root.val写在if前面则return这里写num即可 return num*10 root.val; } // 处理每个数 // 这个num不是总和只是每条路径的数字 num num*10 root.val; // 最后返回所有这种数字的和 return t1(root.left,num) t1(root.right,num); }是否平衡检验二叉树是否平衡平衡定义任何一个节点两棵子树的高度差不超过1利用dfspublic static boolean isBalance(Node root) { // 空树是平衡的 if (root null) { return true; } // 计算左右子树的高度差 int heightDiff getHeight(root.left) - getHeight(root.right); if (heightDiff -1 || heightDiff 1) { return false; // 高度差超过 1不平衡 } // 递归检查左右子树是否平衡 return isBalance(root.left) isBalance(root.right); } // 获取以root为根的树高度 private static int getHeight(Node root) { // 空节点高度定义为 0 if(root null) { return 0; } // 当前节点高度 左右子树最大高度 1 int leftH getHeight(root.left); int rightH getHeight(root.right); return Math.max(leftH, rightH) 1; }高度最低的BST用升序数组构建高度最低的BST二叉查找树因为BST要求小的在左边大的在右边所以在构造的时候不能直接按顺序取数组元素进行构造所以解题关键是如何取元素取元素每次从数组中取中间元素作为根节点递归构造左右子树左右子树的节点元素分别从数组的前一半和后一半取public static Node createBST(int[]arr,int start,int end) { if (start end) return null; int mid (startend)/2; Node root new Node(arr[mid]); root.left createBST(arr,start,mid - 1); root.right createBST(arr,mid 1,end); return root; }某一层的所有节点设计一个链表链表由二叉树的某层中所有节点组成输入root二叉树和depth指定的层次输出链表利用bfsclass Node { int val; Node left; Node right; Node(int val) { this.val val; } } class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }public static ListNode createList(Node root, int depth) { if (root null || depth 1) { return null; } ListNode dummy new ListNode(-1); ListNode tail dummy; // 使用队列进行层次遍历 QueueNode queue new LinkedList(); queue.add(root); int currentDepth 1; // 当前层次 while (!queue.isEmpty()) { int levelSize queue.size(); // 当前层次的节点数 // 如果当前层次是指定层次提取节点并构建链表 //第 n-1 层处理完队列里已经有了第 n 层全部节点 if (currentDepth depth) { for (int i 0; i levelSize; i) { Node curr queue.poll(); tail.next new ListNode(curr.val); // 将节点值加入链表 tail tail.next; } break; // 已经找到指定层次退出循环 } // 如果不是指定层次继续遍历下一层 // 想要继续遍历下一层需要把队列中所有的当前层的节点都出队 // 注意这里面不能单纯的出队 // 还要记得bfs的基本框架出队加入节点的孩子 for (int i 0; i levelSize; i) { Node curr queue.poll(); if (curr.left ! null) { queue.add(curr.left); } if (curr.right ! null) { queue.add(curr.right); } } currentDepth; // 进入下一层 } return dummy.next; // 返回链表的头节点 }判断BST判断二叉树是否是BST当前节点必须小于右子树的最大节点大于左子树的最小节点不能只单单的小于右孩子大于左孩子public static boolean isBST(Node root) { if (root null || (root.left null root.right null)) { return true; } int currLeft root.left ! null ? findMin(root.left).val : -1; int currRight root.right ! null ? findMax(root.right).val : -1; boolean curr root.val currLeft root.val currRight; return isBST(root.left) isBST(root.right) curr; } public static Node findMin(Node root){ if(root.left null){ return root; } return findMin(root.left); } public static Node findMax(Node root){ if(root.right null){ return root; } return findMax(root.right); }判断子树有两棵子树T1和T2判断T2是否是T1的子树遍历T1找一个节点值和T2的根节点值相同。找到后检查剩余节点是否和T2相同相同就是子树不相同就接着找值和T2的根节点值相同的节点// 检查 node1 和 node2 是否完全相同 public boolean check(Node node1, Node node2) { if (node1 null node2 null) { return true; // 两者都为空匹配 } if (node1 null || node2 null) { return false; // 一个为空另一个不为空不匹配 } // 检查当前节点值是否相等并递归检查左右子树 return node1.val node2.val check(node1.left, node2.left) check(node1.right, node2.right); } // 判断 root2 是否是 root1 的子树 public boolean isChild(Node root1, Node root2) { if (root2 null) { return true; // 空树是任何树的子树 } if (root1 null) { return false; // root1 为空但 root2 不为空root2 不可能是 root1 的子树 } // 如果当前节点匹配检查是否是完全相同的子树 if (root1.val root2.val check(root1, root2)) { return true; } // 否则递归检查 root1 的左子树和右子树 return isChild(root1.left, root2) || isChild(root1.right, root2); }和为指定值的路径二叉树每个节点存储一个val输出所有和为指定值的路径这里的路径不需要从根节点开始也不需要到叶子节点结束但路径方向必须是向下的只能从父节点到子节点采用双重递归的方法来解决这个问题第一层递归遍历二叉树的每个节点以二叉树的每个节点作为起始点尝试找出从该节点开始的所有满足路径和等于指定值的路径。第二层递归深度优先搜索DFS对于每个起始节点使用深度优先搜索的方法沿着二叉树的路径向下遍历计算路径上节点值的和当路径和等于指定值时将该路径记录下来。主方法pathSum的作用是遍历二叉树的每个节点并对每个节点调用深度优先搜索方法dfs来寻找满足条件的路径。同时递归地处理左右子树以确保每个节点都被作为起始点进行考虑。private ListListInteger result new ArrayList(); public ListListInteger pathSum(Node root, int sum) { if (root null) { return result; } // 从当前节点开始尝试寻找路径 dfs(root, sum, new ArrayList()); // 递归处理左子树 pathSum(root.left, sum); // 递归处理右子树 pathSum(root.right, sum); return result; }深度优先搜索方法dfs用于从当前节点开始沿着二叉树的路径向下遍历计算路径上节点值的和当路径和等于指定值时将该路径记录下来。private void dfs(TreeNode node, int target, ListInteger path) { if (node null) { return; } // 将当前节点加入路径 path.add(node.val); target - node.val; // 如果当前路径和等于目标值将路径加入结果集 if (target 0) { result.add(new ArrayList(path)); } // 递归处理左子树 dfs(node.left, target, path); // 递归处理右子树 dfs(node.right, target, path); // 回溯移除当前节点 path.remove(path.size() - 1); }需要注意的是将该路径加入结果集时要使用new ArrayList(path)来复制一份路径避免后续修改影响结果。这里的回溯因为我们要检测所有的路径所以每个节点及其子树都要加进path进行判断如果成立就被存储到result不成立不用处理在判断后无论成不成立都要将这个节点删除进行其他同级节点的测试同级节点的测试指的是当前节点的父节点那一级别因为当前节点已经被回溯了连同他的子树们也就都被删除了我们要找出所有路径和等于 7 的路径。当我们从根节点1开始深度优先搜索时首先将1加入path列表然后递归处理左子节点2将2加入path列表此时path列表为[1, 2]。接着递归处理2的左子节点4将4加入path列表此时path列表为[1, 2, 4]路径和为 7记录下该路径[1, 2, 4]。现在我们完成了对节点4的处理需要回到节点2继续探索其右子节点。如果不进行回溯操作path列表仍然是[1, 2, 4]当我们将节点5加入path列表时path列表会变成[1, 2, 4, 5]这显然不符合我们的要求。………………最近公共祖先找出两节点的最近公共祖先最后的公共祖先此二叉树不一定是BST不能用额外的存储空间存储元素树的结构中带parent法一转换为求两个链表的第一个相交节点如何求相交节点看力扣--链表-CSDN博客的第一道题的法三法二假如两节点是p和qp不动q一直.parent去撞p直到为null找到就返回没找到就p.parentq一直.parent去撞p.parent………………树的结构中不带parent法三将某个节点作为树的根节点去search两个节点如果找到了就将哨兵指向这个节点重复上面的操作将每个节点都作为树的根节点这样去search当找不到时返回哨兵法四法三的剪枝不用将每个节点都作为树的根节点去search而是如果两节点分别在当前检验节点的左右子树上则root即为答案如果两节点在当前检验节点的左子树上则递归左子树不用管右子树了如果两节点在当前检验节点的右子树上则递归右子树不用管左子树了法五利用二维数组ArrayList虽然不符合题设但可以学习方法用二维数组存路径节点第一层存通向一个节点的路径另一层存通向另一个节点的路径然后遍历两层找到第一个不相同的节点则他的前一个节点就是答案存路径节点的方法把遍历到的节点存到temp的ArrayList里当遇到那两个节点时就将temp加入res的ArrayList里参考上面的题和为指定值的路径的思路和代码实现