【算法训练营Day15】二叉树part5

最大二叉树

题目链接：654. 最大二叉树

解题逻辑：

这一题与106. 从中序与后序遍历序列构造二叉树很相似，都是通过切割数组完成二叉树的构建，但这题稍微简单一些。

我们可以通过先构建左右子树再拼接上根节点的方式来构建二叉树，所以我们选用后序遍历。接下来通过递归三部曲来分析：

• 递归参数与返回值：我们需要接受递归的返回值用来构建左右子树，所以返回值定为TreeNode，而参数按照题意定位数组即可
• 递归出口
  • 当数组为空的时候直接返回null
  • 当数组的长度为1的时候直接返回这个唯一值的节点即可
• 递归单层逻辑
  • 通过for循环找到数组的最大值以及最大值的索引值
  • 根据最大值的索引对数组进行切分
  • 构造左、右节点
  • 根据最大值创建根节点然后拼接左右节点

代码如下：

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {if(nums.length == 0) return null;else if(nums.length == 1) return new TreeNode(nums[0]);int devideIndex = 0;int max = 0;for(int i = 0;i < nums.length;i++) {if(nums[i] >= max) {devideIndex = i;max = nums[i];}}TreeNode left = constructMaximumBinaryTree(Arrays.copyOfRange(nums,0,devideIndex));TreeNode right;if(devideIndex + 1 > nums.length) right = null;else right = constructMaximumBinaryTree(Arrays.copyOfRange(nums,devideIndex + 1,nums.length));TreeNode root = new TreeNode(max);root.left = left;root.right = right;return root;}
}

合并二叉树

题目链接：617. 合并二叉树

解题逻辑：

本题的核心就是同时对两棵树进行递归遍历，在这里我们选用后序遍历，然后从递归三部曲的角度来分析：

• 递归参数与返回值，参数因为是同时遍历两棵树所以要接收两个树节点，然后返回值就是TreeNode用来返回根节点
• 递归出口：既然是两棵树同时遍历，再根据题目条件，也就是说两棵树的相同位置节点只要有一个不为null，那么就要遍历到，所以在这里我们的出口条件就是只有当两个节点均为null的时候才会推出递归。
• 单层递归逻辑：
  • 递归获得左右节点
  • 根据传入的两个节点，如果有一个不为null，则使用该节点作为根节点
  • 如果都不为null，则将两节点的值相加作为新的根节点

代码如下：

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 == null && root2 == null) return null;TreeNode node;TreeNode left;TreeNode right;if (root1 == null && root2 != null) {node =  new TreeNode(root2.val);left = mergeTrees(null,root2.left);right = mergeTrees(null,root2.right);} else if(root1 != null && root2 == null) {left = mergeTrees(root1.left,null);right = mergeTrees(root1.right,null);node =  new TreeNode(root1.val);} else {left = mergeTrees(root1.left,root2.left);right = mergeTrees(root1.right,root2.right);node =  new TreeNode(root1.val + root2.val);}node.left = left;node.right = right;return node;}
}

二叉搜索树中的搜索

题目链接：700. 二叉搜索树中的搜索

解题逻辑：本题较为简单，直接比较节点值与搜索值，节点值比搜索值大，则往左递归查询，反之向右递归查询。

代码如下：

class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root == null) return null;if(root.val == val) return root;else if(root.val > val) {TreeNode left = searchBST(root.left,val);if (left != null) return left;}else {TreeNode right = searchBST(root.right,val);if (right != null) return right;}return null;}
}

验证二叉搜索树

题目链接：98.验证二叉搜索树

解题逻辑：

首先要明确二叉搜索树的概念是：根节点大于左子树，小于右子树。

很容易错误理解为根节点大于左节点，小于右节点

他还有一个非常重要的特性就是其中序遍历是单调递增的，那么凭借这个特性我们就可以建立初步的思路。

代码如下：

class Solution {long value = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null) return true;boolean left = isValidBST(root.left);if(left == false) return false;if(root.val <= value) return false;else value =  root.val;boolean right = isValidBST(root.right);if(right == false) return false;return true;}
}