leetCode - - - 二叉树
目录
1.前中后序遍历（递归）
2.前中后序遍历（迭代）
3.翻转二叉树（LeetCode 226）
4.最大二叉树（ LeetCode 654 ）
5.平衡二叉树（ LeetCode 110 ）
6.二叉树的最小深度（ LeetCode 111 ）
7.二叉树的最大深度（ LeetCode 104 ）
8.二叉树的最近公共祖先（ LeetCode 236 ）（重点）
9.从前序与中序遍历序列构造二叉树（ LeetCode 105 ）（重点）
10.从中序与后序遍历序列构造二叉树（ LeetCode 106 ）
11.合并二叉树（LeetCode 617）
12.验证二叉搜索树（LeedCode 98）
1.前中后序遍历（递归）
前序
https://leetcode.cn/problems/binary-tree-preorder-traversal/
/*** 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 List<Integer> preorderTraversal(TreeNode root) {List<Integer> list=new ArrayList<>();preorder(root,list);return list;}private void preorder(TreeNode root,List<Integer>list){if(root==null){return;}list.add(root.val);preorder(root.left,list);preorder(root.right,list);}
}中序
https://leetcode.cn/problems/binary-tree-inorder-traversal/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list=new ArrayList();inorder(root,list);return list;}private void inorder(TreeNode root,List<Integer> list){if(root==null){return;}inorder(root.left,list);list.add(root.val);inorder(root.right,list);}
}后序
https://leetcode.cn/problems/binary-tree-postorder-traversal/
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list=new ArrayList();postorder(root,list);return list;}private void postorder(TreeNode root,List<Integer> list){if(root==null){return;}postorder(root.left,list);postorder(root.right,list);list.add(root.val);}
}2.前中后序遍历（迭代）
先整体写出遍历的顺序，然后再根据前中后序的顺序，确定添加到List的时机。三种遍历统一可以使用一个模版
class Solution {public List<Integer> preorderTraversal(TreeNode root) {// 设置一个数组用来保存二叉树前序遍历的结果List<Integer> preorderResult=new ArrayList<>();// 设置一个数组用来保存二叉树中序遍历的结果//List<Integer> inorderResult = new ArrayList<>();// 设置一个数组用来保存二叉树后序遍历的结果//List<Integer> postorderResult = new ArrayList<>();// 设置一个栈，用来保存路径Stack<TreeNode> stack=new Stack<>();// 左代表该节点的左右孩子节点都没有遍历int nodeLeft=1;// 右代表该节点的左孩子节点已经遍历，右孩子节点还没有遍历int nodeRight=2;// 上代表左右孩子节点都已经遍历，需要返回到它的父节点int nodeUp=3;// 每个节点的初始化状态都是从左开始int nodeState=nodeLeft;TreeNode node=root;while(node!=null){if(nodeState==nodeLeft){preorderResult.add(node.val);if(node.left!=null){stack.push(node);node=node.left;}else{nodeState=nodeRight;}}else if(nodeState==nodeRight){// 把当前节点加入到二叉树中序遍历的结果数组中// inorderResult.add(node.val);if(node.right!=null){stack.push(node);node=node.right;nodeState=nodeLeft;}else{nodeState=nodeUp;}}else if(nodeState==nodeUp){// 把当前节点加入到二叉树后序遍历的结果数组中//postorderResult.add(node.val);TreeNode parent=null;if(!stack.isEmpty()){parent=stack.pop();if(parent.left==node){nodeState=nodeRight;}}node=parent;}}return preorderResult;}
}3.翻转二叉树（LeetCode 226）
https://leetcode.cn/problems/invert-binary-tree/description/
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
class Solution {public TreeNode invertTree(TreeNode root) {if(root==null){return null;}if(root.left==null && root.right==null){return root;}TreeNode left=invertTree(root.left);TreeNode right=invertTree(root.right);root.left=right;root.right=left;return root;}
}class Solution {public TreeNode invertTree(TreeNode root) {// 1、递归终止条件一，当前节点为空的时候，就返回 nullif(root == null) return null;// 2、递归终止条件二，当前节点为叶子节点的时候，就返回这个节点if( root.left == null && root.right == null){// 返回这个节点return root;}// 3、把当前这个节点 root 的左子树进行翻转操作TreeNode left = invertTree(root.left);// 4、把当前这个节点 root 的右子树进行翻转操作TreeNode right = invertTree(root.right);// 5、把翻转成功的右子树赋值给 root 的左子树root.left = right;// 6、把翻转成功的左子树赋值给 root 的右子树root.right = left;// 7、返回翻转成功的二叉树的根节点return root;}
}4.最大二叉树（ LeetCode 654 ）
https://leetcode.cn/problems/maximum-binary-tree/description/
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
- 创建一个根节点，其值为
nums中的最大值。 - 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return maxBinaryTreeNode(nums,0,nums.length-1);}private TreeNode maxBinaryTreeNode(int[]nums,int left,int right){if(left>right){return null;}if(left==right){return new TreeNode(nums[left]);}int maxIndex=left;for(int i=left+1;i<right+1;i++){if(nums[i]>nums[maxIndex]){maxIndex=i;}}TreeNode root=new TreeNode(nums[maxIndex]);TreeNode leftNode=maxBinaryTreeNode(nums,left,maxIndex-1);TreeNode rightNode=maxBinaryTreeNode(nums,maxIndex+1,right);root.left=leftNode;root.right=rightNode;return root;}
}5.平衡二叉树（ LeetCode 110 ）
https://leetcode.cn/problems/balanced-binary-tree/
给定一个二叉树，判断它是否是
平衡二叉树:每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false
class Solution {public boolean isBalanced(TreeNode root) {return recur(root)!=-1;}private int recur(TreeNode curNode){if(curNode==null){return 0;}int left=recur(curNode.left);if(left==-1) return -1;int right=recur(curNode.right);if(right==-1) return -1;return Math.abs(left-right)<2 ? Math.max(left,right)+1:-1;}
}class Solution {public boolean isBalanced(TreeNode root) {// 自底向上判断，只要返现有叶子树出现非平衡二叉树的情况，那么就是不是平衡二叉树了return recur(root) != -1;}private int recur(TreeNode curNode) {// 递归终止条件// 如果当前节点 curNode 为空，那么高度就是 0if (curNode == null) return 0;// 递归的计算当前节点 curNode 的左子树高度int left = recur(curNode.left);// 如果发现为 -1，即表示左子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层// 提前终止了后续的判断if(left == -1) return -1;// 递归的计算当前节点 curNode 的右子树高度int right = recur(curNode.right);// 如果发现为 -1，即表示右子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层// 提前终止了后续的判断if(right == -1) return -1;// 1、否则说明在 curNode 的左子树中没有发现不是平衡二叉树的情况// 2、否则说明在 curNode 的右子树中没有发现不是平衡二叉树的情况// 因此计算一下当前节点 curNode 是否是平衡二叉树// 即计算 curNode 的左子树高度与右子树高度差// 如果发现小于 2，那么返回以当前节点 curNode 为根节点的子树的最大高度// 即节点 curNode 的左右子树中最大高度加 1 return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;}
}6.二叉树的最小深度（ LeetCode 111 ）
即为求最短路径
https://leetcode.cn/problems/minimum-depth-of-binary-tree/
class Solution {public int minDepth(TreeNode root) {Queue<TreeNode> nodeTree=new LinkedList<>();if(root==null){return 0;}nodeTree.add(root);int depth=0;while(nodeTree!=null){int size=nodeTree.size();depth++;for(int i=0;i<size;i++){TreeNode node=nodeTree.poll();if(node.left==null && node.right==null){return depth;}if(node.left!=null){nodeTree.add(node.left);}if(node.right!=null){nodeTree.add(node.right);}}}return depth;}
}来一个趴菜现在才知道的知识点。。。虽然此题判断条件中queue != null 和 !queue.isEmpty() 都不会报错。。。
!queue.isEmpty()更准确，queue != null不报错是因为上面有添加root，对queue已经有初始化了。
queue != null 和 !queue.isEmpty() 是两个用于不同目的的检查，它们在代码中的使用情况和意图有所不同。
queue != null 是用来确认队列对象是否已经初始化。它主要用于确保代码在访问队列之前不会引发 NullPointerException。
!queue.isEmpty() 是用来检查队列是否有元素。在尝试访问或操作队列的元素之前进行检查，以确保队列中有数据可以处理。
通常，这两个检查是相辅相成的。在处理队列时，首先需要确认队列对象本身是有效的 (queue != null)，然后检查队列是否包含元素 (!queue.isEmpty())。
class Solution {public int minDepth(TreeNode root) {// 边界情况处理if (root == null) return 0;// 设置一个队列，用来存储二叉树中的元素Queue<TreeNode> nodeQueue = new LinkedList<>();// 队列添加二叉树的根节点nodeQueue.add(root);// 设置 depth 用来保存输出结果int depth = 0;// 遍历队列，直到队列为空，说明访问了二叉树中所有的节点while (!nodeQueue.isEmpty()) {// 用来记录 queue 的长度，即每层节点的个数int size = nodeQueue.size();// 每到一层，深度就 +1depth++;// 使用 for 循环，将 nodeQueue 中的元素统计for (int i = 0; i < size; i++) {// 从 queue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点 TreeNode curNode = nodeQueue.poll();// curNode.left == null && curNode.right == null // 说明是叶子结点// 由于【最小深度是从根节点到最近叶子节点的最短路径上的节点数量】// 直接返回 depth if(curNode.left == null && curNode.right == null){return depth;}// 判断当前节点的左子节点是否有值，如果有，则添加到 nodeQueue 中if (curNode.left != null){nodeQueue.add(curNode.left);} // 判断当前节点的右子节点是否有值，如果有，则添加到 nodeQueue 中 if (curNode.right != null){nodeQueue.add(curNode.right);}}}// 返回 depthreturn depth;}
}
7.二叉树的最大深度（ LeetCode 104 ）
https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
class Solution {public int maxDepth(TreeNode root) {// 如果 root 为空，直接返回 0if(root == null) return 0;// 递归调用 maxDepth，求出当前节点的左子树的最大深度int left = maxDepth(root.left);// 递归调用 maxDepth，求出当前节点的右子树的最大深度int right = maxDepth(root.right);// 求出当前节点的左右子树中较大的值int childMaxDepth = Math.max(left,right);// 二叉树的最大深度就是它的左右子树中较大的值加上 1return childMaxDepth + 1;}
}8.二叉树的最近公共祖先（ LeetCode 236 ）（重点）
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null) return null;if(root==p) return p;if(root==q) return q;TreeNode left=lowestCommonAncestor(root.left,p,q);TreeNode right=lowestCommonAncestor(root.right,p,q);if(left==null && right==null){return null;}else if(left==null){return right;}else if(right==null){return left;}else{return root;}}
}class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 1、如果此时访问的节点 root 为 null，那么直接返回 nullif(root == null ) return null;// 2、如果此时访问的节点 root 为指定节点 p，那么返回 p 这个节点if(root == p) return p;// 3、如果此时访问的节点 root 为指定节点 q，那么返回 q 这个节点if(root == q) return q;// 4、经过上面 1、2、3 的判断之后，root 这个节点必然不是 p、q、null 这三种情况的节点// 接下来，去递归的判断当前节点 root 的左右子树是否包含 p 、q 这两个指定节点// 5、递归的去查找 root 的左子树，判断是否包含p 、q 这两个指定节点// 如果 root 的左子树节点和它的左子树所有节点中包含 p，那么 left 的值就是 p// 如果 root 的左子树节点和它的左子树所有节点中包含 q，那么 left 的值就是 q// 如果 root 的左子树节点和它的左子树所有节点中既不包含 p，也不包含 q，那么 left 的值就是 nullTreeNode left = lowestCommonAncestor(root.left, p, q);// 6、递归的去查找 root 的右子树，判断是否包含p 、q 这两个指定节点// 如果 root 的右子树节点和它的右子树所有节点中包含 p，那么 right 的值就是 p// 如果 root 的右子树节点和它的右子树所有节点中包含 q，那么 right 的值就是 q// 如果 root 的右子树节点和它的右子树所有节点中既不包含 p，也不包含 q，那么 right 的值就是 nullTreeNode right = lowestCommonAncestor(root.right, p, q);// 7、判断完当前节点 root 、 root 的左子树 left、root 的右子树 right 的情况后// 开始向父节点传递信息// 8、如果 root 节点的左子树 left 和右子树 right 都没有找到指定节点 p、q// 并且 root 自己本身也不是指定节点 p、q// 那么它给父节点传递的信息就是以 root 为根节点的那颗二叉树没有指定节点 p、q if(left == null && right == null){// 返回 null，告诉 root 的父节点，这里没找到指定节点 p、qreturn null;// 9、如果在 root 节点的左子树 left 中没有找到指定节点 p、q // 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q 完全取决于 right 了}else if(left == null){// 返回 right ，告诉 root 的父节点，能不能找到指定节点 p、q 完全取决于 right return right;// 10、如果在 root 节点的右子树 right 中没有找到指定节点 p、q // 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q 完全取决于 left 了}else if(right == null){// 返回 left ，告诉 root 的父节点，能不能找到指定节点 p、q 完全取决于 left return left;// 11、此时，left != null 并且 right != null// 这说明在以 root 节点为根节点的那棵二叉树中找到了指定节点 p ，也找到了指定节点 q // 那么就告诉父节点，root 就是 p、q 的最近公共祖先}else{// 返回 root ，告诉 root 的父节点，root 就是 p、q 的最近公共祖先return root;} }
}9.从前序与中序遍历序列构造二叉树（ LeetCode 105 ）（重点）
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {HashMap<Integer,Integer> map=new HashMap<>();for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}TreeNode root=new TreeNode(preorder[0]);for(int i=1;i<preorder.length;i++){TreeNode node=new TreeNode(preorder[i]);insert(root,node,map);}return root;}private void insert(TreeNode root,TreeNode node,HashMap<Integer,Integer> map){while(node!=root){if(map.get(node.val)<map.get(root.val)){ if(root.left==null){root.left=node;}root=root.left;}else{if(root.right==null){root.right=node;}root=root.right;}}}
}class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {// 题目中说 preorder 和 inorder 均无重复元素// 通过哈希表把中序遍历序列中的值和顺序建立映射关系HashMap<Integer, Integer> map = new HashMap<>();// 通过 for 循环，遍历完中序遍历序列中的所有元素for (int i = 0; i < inorder.length; i++) {// 以中序序列中的元素值 inorder[i] 作为 key// 以位置 i 作为 value// 存放到哈希表中// 比如中序遍历序列中的元素是 [ A , D , E , F , G , H , M , Z ]// 那么这个哈希表就是以下的样子// | 索引 | 位置 |// | A | 0 |// | D | 1 |// | E | 2 | // | F | 3 | // | G | 4 | // | H | 5 | // | M | 6 | // | Z | 7 | map.put(inorder[i], i);}// 下面开始构建二叉树// 把前序遍历序列中的第一个元素 preorder[0] 作为二叉树的根节点// 因为任意二叉树的前序遍历序列中的第一个元素，一定是二叉树的根节点TreeNode root = new TreeNode(preorder[0]);// 继续遍历前序遍历序列中的其它元素for(int i = 1 ; i < preorder.length ; i++){// 把当前遍历的元素构造为一个二叉树的节点TreeNode node = new TreeNode(preorder[i]);// 把构造的节点插入到以 root 为根节点的二叉树中insertNode(root,node,map);}// 当 preorder 中所有元素都构造并且插入完毕之后// 二叉树就完成了构建return root;}// root : 二叉树的根节点// node : 待插入的节点// map : 节点值和中序遍历序列位置的映射private void insertNode(TreeNode root,TreeNode node,HashMap<Integer,Integer> map){// 当 root 和 node 指向的节点相同时，跳出循环while(root != node){// 如果 node 的中序遍历序列位置小于 root 的中序遍历序列位置// 说明 node 应该在 root 的左子树中if(map.get(node.val) < map.get(root.val)){// 如果此时 root 没有左子树if(root.left == null){// 那么就把 node 设置为 root 的左子树root.left = node;}// 1、如果之前 root 没有左子树，那么通过上面的代码，就设置好了 root 的左子树// 也就是说 node 是 root 的一个叶子节点，完成了插入操作// 把 root 指向 root.left 后，root 为 node，跳出了循环// 2、如果之前 root 已经有左子树，那么就不能直接把 node 插入到 root 的左子树上// 需要判断应该把 node 插入到 root 左子树上的孩子节点的那个位置上// 比如现在的 root 是这个样子，node 为 A// G// /// D// / \// ① ②// root 已经有左子树 D 了，所以 node 应该考虑插入到 D 中的 ① 还是 ② 上面// 所以，把 root 指向 root.left ，继续遍历 root 的左子树的情况root = root.left;}else{// 如果 node 的中序遍历序列位置大于 root 的中序遍历序列位置// 说明 node 应该在 root 的右子树中// 如果此时 root 没有右子树if(root.right == null){// 那么就把 node 设置为 root 的右子树root.right = node;}// 把 root 指向 root.right ，继续遍历 root 的右子树的情况root = root.right;}}}
}10.从中序与后序遍历序列构造二叉树（ LeetCode 106 ）
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
与上面前中构造基本一致，不同的是后序数组从后往前遍历，后序数组的最后一个值，为整棵树的根节点。
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {HashMap<Integer,Integer> map=new HashMap<>();for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}TreeNode root=new TreeNode(postorder[postorder.length-1]);for(int i=postorder.length-2;i>=0;i--){TreeNode node=new TreeNode(postorder[i]);insert(root,node,map);}return root;}private void insert(TreeNode root,TreeNode node,HashMap<Integer,Integer> map){while(node!=root){if(map.get(node.val)<map.get(root.val)){ if(root.left==null){root.left=node;}root=root.left;}else{if(root.right==null){root.right=node;}root=root.right;}}}
}11.合并二叉树（LeetCode 617）
https://leetcode.cn/problems/merge-two-binary-trees/description/
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null && root2==null){return null;}if(root1==null){return root2;}if(root2==null){return root1;}TreeNode mergeNode=new TreeNode(root1.val+root2.val);mergeNode.left=mergeTrees(root1.left,root2.left);mergeNode.right=mergeTrees(root1.right,root2.right);return mergeNode;}
}12.验证二叉搜索树（LeedCode 98）
https://leetcode.cn/problems/validate-binary-search-tree/
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
解法一：中序遍历+比较数组是否单调递增
//二叉搜索树的中序遍历，节点的值一定是单调递增的//将二叉搜索树的中序遍历的值存放在数组中//判断这个数组是否是单调递增的
class Solution {public boolean isValidBST(TreeNode root) {List<Integer> list=new ArrayList<>();inorderTree(root,list);return isCreasing(list);}private void inorderTree(TreeNode root,List<Integer> list){if(root==null){return;}inorderTree(root.left,list);list.add(root.val);inorderTree(root.right,list);}private boolean isCreasing(List<Integer> list){for(int i=1;i<list.size();i++){if(list.get(i)<=list.get(i-1)){return false;}}return true;}
}解法二：中序遍历+双指针
相比上种方法，少了一步存放各个节点的值。在中序遍历的过程中，每次比较当前应该节点和当前节点的大小即可。
class Solution {public boolean isValidBST(TreeNode root) {return inorderTree(root);}//如果当前节点为空，则返回 true。这是递归的终止条件，也表明空节点是有效的 BST。TreeNode pre=null;private boolean inorderTree(TreeNode root){if(root==null){return true;}//首先递归遍历当前节点的左子树。如果左子树不符合 BST 的条件（返回 false），则当前树也不符合 BST 的条件，返回 false。if(!inorderTree(root.left)){return false;}//prev != null：确保 prev 已经被初始化，检查当前节点值 node.val 是否大于前一个节点的值prev.valif(pre!=null && root.val<=pre.val){return false;}//更新 prev 为当前节点，以便在接下来的遍历中进行比较pre=root;//遍历当前节点的右子树。如果右子树不符合 BST 的条件（返回 false），则返回 false；否则，返回 truereturn inorderTree(root.right);}
}