654. Maximum Binary Tree
You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:
- Create a root node whose value is the maximum value in
nums. - Recursively build the left subtree on the subarray prefix to the left of the maximum value.
- Recursively build the right subtree on the subarray suffix to the right of the maximum value.
Return the maximum binary tree built from nums.
Example 1:
Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
- The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
- Empty array, so no child.
- The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
- Empty array, so no child.
- Only one element, so child is a node with value 1.
- The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
- Only one element, so child is a node with value 0.
- Empty array, so no child.
Example 2:
Input: nums = [3,2,1]
Output: [3,null,2,null,1]
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1000- All integers in
numsare unique.
先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
最大值所在的下标左区间 构造左子树
最大值所在的下标右区间 构造右子树
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructMaximumBinaryTree1(nums, 0, nums.length);
}
public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
if (rightIndex - leftIndex < 1) {// 没有元素了
return null;
}
if (rightIndex - leftIndex == 1) {// 只有一个元素
return new TreeNode(nums[leftIndex]);
}
int maxIndex = leftIndex;// 最大值所在位置
int maxVal = nums[maxIndex];// 最大值
for (int i = leftIndex + 1; i < rightIndex; i++) {
if (nums[i] > maxVal){
maxVal = nums[i];
maxIndex = i;
}
}
TreeNode root = new TreeNode(maxVal);
// 根据maxIndex划分左右子树
root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
return root;
}
}
For Future References
题目链接：https://leetcode.com/problems/maximum-binary-tree/
文章讲解：https://programmercarl.com/0654.最大二叉树.html
617. Merge Two Binary Trees
You are given two binary trees root1 and root2.
Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.
Return the merged tree.
Note: The merging process must start from the root nodes of both trees.
Example 1:
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
Example 2:
Input: root1 = [1], root2 = [1,2]
Output: [2,2]
Constraints:
- The number of nodes in both trees is in the range
[0, 2000]. 104 <= Node.val <= 104
因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了啊（如果t2也为NULL也无所谓，合并之后就是NULL）。
反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。
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;
}
}
For Future References
题目链接：https://leetcode.com/problems/merge-two-binary-trees/
文章讲解：https://programmercarl.com/0617.合并二叉树.html
700. Search in a Binary Search Tree
You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.
Example 1:
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
Example 2:
Input: root = [4,2,7,1,3], val = 5
Output: []
Constraints:
- The number of nodes in the tree is in the range
[1, 5000]. 1 <= Node.val <= 107rootis a binary search tree.1 <= val <= 107
二叉搜索树是一个有序树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树
如果root.val > val，搜索左子树，如果root.val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。
class Solution {
// 递归，普通二叉树
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
TreeNode left = searchBST(root.left, val);
if (left != null) {
return left;
}
return searchBST(root.right, val);
}
}
class Solution {
// 递归，利用二叉搜索树特点，优化
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (val < root.val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
}
For Future References
题目链接：https://leetcode.com/problems/search-in-a-binary-search-tree/
文章讲解：https://programmercarl.com/0700.二叉搜索树中的搜索.html
98. Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. 231 <= Node.val <= 231 - 1
注意二叉搜索树中不能有重复元素
比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。
一直更新maxVal，一旦发现maxVal >= root.val，就返回false，注意元素相同时候也要返回false。
class Solution {
// 递归
TreeNode max;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
// 左
boolean left = isValidBST(root.left);
if (!left) {
return false;
}
// 中
if (max != null && root.val <= max.val) {
return false;
}
max = root;
// 右
boolean right = isValidBST(root.right);
return right;
}
}
For Future References
题目链接：https://leetcode.com/problems/validate-binary-search-tree/
文章讲解：https://programmercarl.com/0098.验证二叉搜索树.html
标签：node,20,val,nums,随想录,700,return,null,root From： https://www.cnblogs.com/bluesociety/p/16777959.html