DEV Community 👩‍💻👨‍💻

Cover image for 代码随想录day20 | 654.Maximum BT, 617.Merge Two Binary Trees, 700.Search in a Binary Search Tree, 98.Validate BST
Ming
Ming

Posted on

代码随想录day20 | 654.Maximum BT, 617.Merge Two Binary Trees, 700.Search in a Binary Search Tree, 98.Validate BST

leetcode 654 - Maximum Binary Tree

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:

  • 二叉树的根是数组中的最大元素
  • 左子树是通过数组中最大值左边部分构造出的最大二叉树
  • 右子树是通过数组中最大值右边部分构造出的最大二叉树 通过给定的数组构建最大二叉树,并且输出这个树的根节点.

Image description

这个题还是构造二叉树之类,递归构造二叉树时,递归参数多是切割后的数组,返回值一般都是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;
};
Enter fullscreen mode Exit fullscreen mode

leetcode 617 - Merge Two Binary Trees

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点

Image description

这个题参数是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;
};

Enter fullscreen mode Exit fullscreen mode

leetcode 700 - Search in a Binary Search Tree

给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL

Image description

在上述示例中,如果要找的值是 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);
};
Enter fullscreen mode Exit fullscreen mode
/* 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
};

Enter fullscreen mode Exit fullscreen mode

98. Validate Binary Search Tree

给定一个二叉树,判断其是否是一个有效的二叉搜索树。
一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

Image description

这道题考点就是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;
};

Enter fullscreen mode Exit fullscreen mode
//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);
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Create an Account!

👀 Just want to lurk?

That's fine, you can still create an account and turn on features like 🌚 dark mode.