Leetcode 654.最大二叉树

题目：654.最大二叉树

初始思路

和根据前（后）序和中序遍历构建二叉树一样，都是找到根节点，然后递归建立树。

代码

  1. var constructMaximumBinaryTree = function (nums) {
  2.     const BuildTree = (arr, left, right) => {
  3.         if (left > right) {
  4.             return null
  5.         }
  6.         // 找到数组中的最大值和对应的下标，构建这部分的根节点
  7.         let maxValue = -1
  8.         let maxIndex = -1
  9.         for (let i = left; i <= right; i++) {
  10.             if (arr[i] > maxValue) {
  11.                 maxValue = arr[i]
  12.                 maxIndex = i
  13.             }
  14.         }
  15.         let root = new TreeNode(maxValue)
  16.         // 从maxIndex这里进行分割
  17.         root.left = BuildTree(arr, left, maxIndex - 1)
  18.         root.right = BuildTree(arr, maxIndex + 1, right)
  19.         return root
  20.     }
  21.     let root = BuildTree(nums, 0, nums.length - 1)
  22.     return root
  23. };

感想

  1. 思路挺简单的，也挺常规，就是代码要好好写。

Leetcode 617.合并二叉树

题目：617.合并二叉树

初始思路

第一反应是可以用层序遍历模板

代码

  1. var mergeTrees = function (root1, root2) {
  2.     const preOrder = (root1, root2) => {
  3.         if (!root1) return root2
  4.         if (!root2) return root1
  5.         root1.val += root2.val
  6.         root1.left = preOrder(root1.left, root2.left)
  7.         root1.right = preOrder(root1.right, root2.right)
  8.         return root1
  9.     }
  10.     return preOrder(root1, root2)
  11. }
  1. var mergeTrees = function (root1, root2) {
  2.     if (!root1) return root2
  3.     if (!root2) return root1
  4.     // 规定以root1为基准进行修改
  5.     let queue = []
  6.     queue.push(root1)
  7.     queue.push(root2)
  8.     while (queue.length) {
  9.         let node1 = queue.shift()
  10.         let node2 = queue.shift()
  11.         node1.val += node2.val
  12.         if (node1.left != null && node2.left != null) {
  13.             queue.push(node1.left)
  14.             queue.push(node2.left)
  15.         }
  16.         if (node1.right != null && node2.right != null) {
  17.             queue.push(node1.right)
  18.             queue.push(node2.right)
  19.         }
  20.         if (node1.left == null && node2.left != null) {
  21.             node1.left = node2.left
  22.         }
  23.         if (node1.right == null && node2.right != null) {
  24.             node1.right = node2.right
  25.         }
  26.     }
  27.     return root1
  28. };

感想

  1. 递归也简单，为什么我的第一反应是用层序遍历。

Leetcode 700.二叉搜索树中的搜索

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

初始思路

根据二叉搜索树的定义就OK了吧，加递归。

代码

  1. var searchBST = function (root, val) {
  2.     if (!root || root.val === val) {
  3.         return root
  4.     }
  5.     else if (root.val > val) {
  6.         // 在左子树中继续找
  7.         return searchBST(root.left, val)
  8.     } else if (root.val < val) {
  9.         // 在右子树中继续找
  10.         return searchBST(root.right, val)
  11.     }
  12. };
  1. var searchBST = function (root, val) {
  2.     while (!root) {
  3.         if (root.val > val) {
  4.             root = root.left
  5.         } else if (root.val < val) {
  6.             root = root.right
  7.         } else {
  8.             return root
  9.         }
  10.     }
  11.     return null
  12. }

感想

  1. 复习一下二叉搜索树的定义。
  2. 二叉搜索树：
    1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    3. 它的左、右子树也分别为二叉排序树

Leetcode 98.验证二叉搜索树

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

初始思路

一看题目，一眼递归。

代码

  1. var isValidBST = function (root) {
  2.     let arr = []
  3.     const buildArr = (root) => {
  4.         if (root) {
  5.             // 前 中 后
  6.             buildArr(root.left)
  7.             arr.push(root.val)
  8.             buildArr(root.right)
  9.         }
  10.     }
  11.     buildArr(root)
  12.     for (let i = 1; i < arr.length; i++){
  13.         if (arr[i] <= arr[i - 1]) {
  14.             return false
  15.         }
  16.     }
  17.     return true
  18. };

感想

  1. 递归中序遍历将二叉搜索树转变成一个数组，然后判断这个数组是否有序。利用了二叉搜索树的特性。