654.最大二叉树
题目链接：力扣
思路
一开始将代码写了出来，但是因为少了一个终止条件一直报下标超出的错误，写递归代码的时候一定要将终止条件的所有情况都要想清楚
构建一个二叉树的时候应该使用前序遍历，因为只有创建了中间节点，才能继续船舰左节点和右节点
最大二叉树
第一步：终止条件
数组中没有元素的情况
数组中只有一个元素的情况
第二步：选择出数组中的最大值，创建节点
第三步：递归左数组，递归右数组
class Solution { public TreeNode constructMaximumBinaryTree(int[] nums) { return construct(nums,0,nums.length); } public TreeNode construct(int[] nums, int indexBegin, int indexEnd){ if (indexEnd - indexBegin < 1) { return null; } if (indexEnd - indexBegin == 1) { return new TreeNode(nums[indexBegin]); } int maxIndex = indexBegin; int maxVal = nums[indexBegin]; for (int i = indexBegin + 1; i < indexEnd;i++) { if (nums[i] > maxVal) { maxVal = nums[i]; maxIndex = i; } } TreeNode root = new TreeNode(maxVal); root.left = construct(nums,indexBegin,maxIndex); root.right = construct(nums,maxIndex + 1,indexEnd); return root; } }
617.合并二叉树
题目链接：力扣
思路
合并两个二叉树使用前序遍历最好理解，是最直接的思维方式
实际递归的前中后都是可以的，中的处理逻辑改变顺序就改变了遍历的顺序
合并二叉树
递归法
只要这个终止条件想明白了 这道题目就很简单
第一步：确定参数和返回值
第二步：终止条件
第三步：如果root1为空，返回root2;如果root2为空，返回root1
第四步：直接在root1树上进行改变 (也可以定义新的二叉树)
class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) {return root2;} if (root2 == null) {return root1;} root1.val += root2.val; root1.left = mergeTrees(root1.left,root2.left); root1.right = mergeTrees(root1.right,root2.right); return root1; } }
迭代法
使用层序遍历模拟也比较方便，只要搞清楚，当一个为空的时候怎么处理就可以
class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) {return root2;} if (root2 == null) {return root1;} // 创建队列 Deque<TreeNode> deque = new LinkedList<>(); // 先将两个根节点加入队列中，代码能走到这里说明两个根节点都不为空 deque.offer(root1); deque.offer(root2); // 对队列中的节点进行操作 while (!deque.isEmpty()) { TreeNode node1 = deque.poll(); TreeNode node2 = deque.poll(); node1.val += node2.val; if (node1.left != null && node2.left != null) { deque.offer(node1.left); deque.offer(node2.left); } if (node1.right != null && node2.right != null) { deque.offer(node1.right); deque.offer(node2.right); } // 然后剩下的就只判断t1这边是空的情况 // 因为如果t1为空，就全看t2了 if (node1.left == null && node2.left != null) { node1.left = node2.left; } if (node1.right == null && node2.right != null) { node1.right = node2.right; } // 如果是t1不为空，t2为空，那就不做任何改变就可以了 } return root1; } }
700.二叉搜索树中的搜索
题目链接:力扣
思路
可以说是做二叉树以来最简单的题目了
二叉搜索树中的搜索
递归法
class Solution { public TreeNode searchBST(TreeNode root, int val) { if (root == null || root.val == val) { return root; } if (root.val > val && root.left != null) { return searchBST(root.left,val); } if (root.val < val && root.right != null) { return searchBST(root.right,val); } return null; } }
迭代法
借助队列和不记住队列的写法
class Solution { public TreeNode searchBST(TreeNode root, int val) { Deque<TreeNode> deque = new LinkedList<>(); deque.offer(root); while (!deque.isEmpty()) { int len = deque.size(); for (int i = 0; i < len; i++) { TreeNode node = deque.poll(); if (node.val == val) { return node; } if (node.left != null) { deque.offer(node.left); } if (node.right != null) { deque.offer(node.right); } } } return null; } }
class Solution { public TreeNode searchBST(TreeNode root, int val) { while (root != null) { if (val < root.val) { root = root.left; } else if (val > root.val) { root = root.right; } else { return root; } } return null; } }
98.验证二叉搜索树
题目链接:力扣
思路
应该判断每个节点的左右节点是否符合二叉搜索树的排序
二叉搜索树中不能有重复的元素
验证二叉搜索树
递归法
递归法有两种思路：
1、二叉搜索树是有序的，使用中序遍历就可以获得一个有序的数组，判断这个数组是否有序就可以
2、不使用数组，利用二叉树直接递归，也是可以的，但是会有两个陷阱问题：
陷阱一：不能单纯比较左节点小于中间节点，右节点大于中间节点就完事了
我们需要比较的是： 左子树所有节点小于中间节点，右子树所有节点大于中间节点
陷阱二：题目中的元素出现比int范围小的值
使用数组判断：
class Solution { List<Integer> nums = new ArrayList<>(); public boolean isValidBST(TreeNode root) { treaversal(root , nums); for (int i = 0; i + 1 < nums.size(); i++) { if (nums.get(i) >= nums.get(i + 1)) { return false; } } return true; } // 使用中序遍历将二叉树中的元素添加到数组中 public void treaversal(TreeNode root,List<Integer> nums) { if (root == null) { return; } treaversal(root.left,nums); nums.add(root.val); treaversal(root.right,nums); } }
使用递归按从小到大的顺序判断：
class Solution { private long prev = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if (root == null) { return true; } if (!isValidBST(root.left)) { return false; } if (root.val <= prev) { // 不满足搜索二叉树的情况 return false; } prev = root.val; if (!isValidBST(root.right)) { return false; } return true; } }
使用递归（双指针）：
class Solution { TreeNode pre = null; // 用来记录前一个节点 public boolean isValidBST(TreeNode root) { if (root == null) { return true; } boolean left = isValidBST(root.left); if (pre != null && pre.val >= root.val) { return false; } pre = root; // 记录前一个节点 boolean right = isValidBST(root.right); return left && right; } }
