654.最大二叉树
文字讲解:最大二叉树
视频讲解:最大二叉树
状态:ok
思路:
1、这题和昨天的,通过中序和后序遍历构建二叉树类似,此题相当于通过前序来构建二叉树;但是通过中序和后序来构建二叉树,需要借助两个数组来完成,而此题则需要仅需一个数据可完成;
2、先取数组中的最大值,获取其下标,按照该下标将数组分为左右两个数组,分别为左子树和右子树的元素。
3、然后分别按照步骤2进行递归构建该二叉树并且返回;
class Solution {
Map<Integer, Integer> valMap = new HashMap<>();
public TreeNode constructMaximumBinaryTree(int[] nums) {
for (int i = 0; i < nums.length; i++) {
valMap.put(nums[i], i);
}
return buildMaxTree(nums, 0, nums.length-1);
}
public TreeNode buildMaxTree(int[] nums, int startIndex, int endIndex) {
if (startIndex > endIndex) {
return null;
}
Integer maxNodeVal = getMaxNodeVal(nums, startIndex, endIndex);
Integer index = valMap.get(maxNodeVal);
TreeNode root = new TreeNode(maxNodeVal);
root.left = buildMaxTree(nums, startIndex, index-1);
root.right = buildMaxTree(nums, index+1, endIndex);
return root;
}
public Integer getMaxNodeVal(int[] nums, int startIndex, int endIndex) {
int max = Integer.MIN_VALUE;
for (int i = startIndex; i <= endIndex; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
return max;
}
}
617.合并二叉树
文字讲解:合并二叉树
视频讲解:代码随想录-合并二叉树
状态:看到这道题有点懵逼,不知道如何下手
思路:
1、强调一下 – T^T — ,递归三部曲,确定好入参,确定好退出条件,确认单层递归逻辑;二刷时不明白再看视频继续加深印象;
代码:
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
return rightMergeLeftTree(root1, root2);
}
public TreeNode rightMergeLeftTree(TreeNode leftNode, TreeNode rightNode) {
if (leftNode == null) return rightNode;
if (rightNode == null) return leftNode;
//当两个node都不为空的时候
leftNode.val = leftNode.val + rightNode.val;
leftNode.left = rightMergeLeftTree(leftNode.left, rightNode.left);
leftNode.right = rightMergeLeftTree(leftNode.right, rightNode.right);
return leftNode;
}
}
700.二叉搜索树中的搜索
文字讲解:二叉搜索树中的搜索
视频讲解:代码随想录-二叉搜索树中的搜索
状态:这题so easy了
思路:
1、递归三部曲,入参已确定,判断退出条件为节点为空的时候,递归逻辑为,先判断当前节点的val是否等于搜索值,等于则返回,不等则判断当前node的val比是否比搜索值大,如果大则搜索right子节点,否则搜索left左节点;
代码:
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) return null;
if (root.val == val) {
return root;
}
if (root.val > val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
}
98.验证二叉搜索树(重要)
文字讲解:验证二叉搜索树
视频讲解: 代码随想录-验证二叉搜索树
状态:
思路:
1、这题真是给坑就踩进去了,BSF不是简单的理解为每个节点的左子树的值比父节点小,每个节点的右子树比父节点大,而是父节点比左子树的左右节点都大,比右子树的所有节点都小;因为没有考虑全,所以感觉自己没问题,结果调试后一直通过不了;
2、这题通过中序遍历的方式完成,仔细体会代码还能熟悉一下方法栈的调用过程;
3、另外此题还能通过中序遍历将各节点元素收集到一个数组中,然后判断改数组是否是有序的;
代码:
//通过中序遍历+递归的方式判断
class Solution {
Long maxValue = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
//如果到叶子节点了,则直接返回true;
if (root == null) {
return true;
}
boolean leftFlag = isValidBST(root.left);
if (root.val > maxValue) {
maxValue = Long.valueOf(root.val);
} else {
return false;
}
boolean rightFlag = isValidBST(root.right);
return leftFlag && rightFlag;
}
}
//通过中序遍历收集数组的方式判断
class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return true;
}
List<Integer> params = new ArrayList<>();
//通过中序遍历收集二叉树元素
collectParams(root, params);
return validListSorted(params);
}
public void collectParams(TreeNode node, List<Integer> params) {
if (node == null) {
return;
}
collectParams(node.left, params);
//收集元素
params.add(node.val);
collectParams(node.right, params);
}
public boolean validListSorted(List<Integer> list) {
int left = 0;
int right = 1;
while (right <= list.size()-1) {
if (list.get(left) >= list.get(right)) {
return false;
}
left++;
right++;
}
return true;
}
}