leetcode 654 - Maximum Binary Tree
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:
- 二叉树的根是数组中的最大元素
- 左子树是通过数组中最大值左边部分构造出的最大二叉树
- 右子树是通过数组中最大值右边部分构造出的最大二叉树 通过给定的数组构建最大二叉树，并且输出这个树的根节点.
这个题还是构造二叉树之类，递归构造二叉树时，递归参数多是切割后的数组，返回值一般都是tree node, 这点要注意，这道题使用pre_order构造
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
// 递归参数就是传入的是存放元素的数组，返回该数组构造的二叉树的头结点：
var constructMaximumBinaryTree = function (nums) {
//递归终止条件：当构造到叶子节点时候
if (nums.length === 1) return new TreeNode(nums[0]); // 注意return是node
/*构造中间节点*/
let maxVal = -Infinity;
let maxValIndex = -1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] > maxVal) {
maxVal = nums[i];
maxValIndex = i;
}
}
let node = new TreeNode(maxVal); // middle node
/*递归构造左子树：*/
if (maxValIndex > 0) {
node.left = constructMaximumBinaryTree(nums.slice(0, maxValIndex)); // 切割数组
}
/*递归构造右子树：*/
if (maxValIndex < nums.length - 1) {
node.right = constructMaximumBinaryTree(nums.slice(maxValIndex + 1)); // 切割数组
}
return node;
};
leetcode 617 - Merge Two Binary Trees
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点
这个题参数是2个树，类似这道题的还有lc-100(same tree), lc101(is symmetric),lc572(isSubtree), 递归套路都差不多，区别点在递归返回值是什么，类似lc100,lc101,lc572递归返回boolean, 这道题不同返回值是tree node.
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root1
* @param {TreeNode} root2
* @return {TreeNode}
*/
//递归参数是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
var mergeTrees = function (root1, root2) {
//确定终止条件：
if (root1 === null) return root2;
if (root2 === null) return root1;
// 确定单层递归的逻辑：
let newRoot = new TreeNode(root1.val + root2.val);
newRoot.left = mergeTrees(root1.left, root2.left);
newRoot.right = mergeTrees(root1.right, root2.right);
return newRoot;
};
leetcode 700 - Search in a Binary Search Tree
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
二叉搜索树是一个有序树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树
这就决定了BST递归和迭代遍历和普通二叉树都不一样,所以这道题就不要使用dfs的pre/in/post order了，直接根据BST的顺序特性来搜索
/* Solution1: Recursion, 根据BST的顺序特性来搜索的,这里就用不上DFS preorde,postorder,inorder了*/
var searchBST = function (root, val) {
//确定终止条件
if (!root || root.val === val) return root;
//说明val有可能在左子树里
if (val < root.val) return searchBST(root.left, val);
//说明val有可能在右子树里
if (val > root.val) return searchBST(root.right, val);
};
/* Solution2: iteration, 根据BST的顺序特性来搜索的 */
var searchBST = function (root, val) {
while (root) {
if (val < root.val) {
root = root.left;
} else if (val > root.val) {
root = root.right;
} else {
return root; // found it
}
}
return null; // not found
};
98. Validate Binary Search Tree
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
这道题考点就是BST的in-order(中序)遍历是一个递增的数组
//Solution 1: DFS Inorder traversal, then see if array is increasing as expected?
var isValidBST = function (root) {
const visited = [];
const helper = (node) => {
if (!node) return true;
if (node.left) helper(node.left); //left
visited.push(node.val); // middle
if (node.right) helper(node.right); // right
};
helper(root);
for (let i = 0; i < visited.length; i++) {
if (visited[i + 1] <= visited[i]) return false; //array is not increasing. so not a BST
}
return true;
};
//Solution 2: DFS Inorder traversal without array assistance
var isValidBST = function (root) {
let pre = null; //用pre记录前一个节点
const inOrder = (node) => {
if (node === null) return true;
let left = inOrder(node.left);
if (pre && pre.val >= node.val) return false; //inorder左中右，prev.val要是比现在节点大，那说明不是BST了
pre = node; //inorder左中右，prev.val比现在节点小，则继续update pre
let right = inOrder(node.right);
return left && right;
};
return inOrder(root);
};
Top comments (0)