代码随想录第17天 | 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

654.最大二叉树

/* 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 === 0) return nulllet m = Math.max(...nums);let x = nums.indexOf(m)const root = new TreeNode(m, constructMaximumBinaryTree(nums.slice(0, x)), constructMaximumBinaryTree(nums.slice(x + 1))); // 创建中间节点return root
};

第一想法

如代码

困难

• slice的左右区间注意，[ , )，左闭右开

617.合并二叉树

/* 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 && root2) {  //1不行 2行，直接返回2，不进行后面的节点相加操作了return root2;}if ((root1 && root2 == null) || (root1 == null && root2 == null)) {  //1行2不行，返回1；或者都不行，返回1也就是nullreturn root1;}//都行const root =new TreeNode(root1.val+root2.val, mergeTrees(root1.left,root2.left),mergeTrees(root1.right,root2.right)) // 创建中间节点return root  
};

第一想法

递归

 const root =new TreeNode(root1.val+root2.val, mergeTrees(root1.left,root2.left),mergeTrees(root1.right,root2.right)) // 创建中间节点return root  

困难

• 结束条件

if (root1 == null && root2) {
//1不行 2行，直接返回2，不进行后面的节点相加操作了
return root2;
}
if ((root1 && root2 == null) || (root1 == null && root2 == null)) {
//1行2不行，返回1；或者都不行，返回1也就是null
return root1;
}

700.二叉搜索树中的搜索

/* 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} root* @param {number} val* @return {TreeNode}*/
var searchBST = function(root, val) { //自己的写法if(!root) return null;const st=[root] //栈，pop(),push()while(st.length){  //let x=st.pop();	//每次遍历输出，把右左孩子入栈if(x.val===val)return xx.right &&st.push(x.right) //很重要，不然下一次遍历x.val会出错x.left &&st.push(x.left)}return null
};
var searchBST = function(root, val) {while (root) {if (val === root.val) {return root;}root = val < root.val ? root.left : root.right;}return null;
};
//作者：迭代法力扣官方题解*
var searchBST = function(root, val) {if (!root) {return null;}if (val === root.val) {return root;}return searchBST(val < root.val ? root.left : root.right, val);
};//作者：回调法力扣官方题解

第一想法

前序遍历就行了，不管是迭代法还是回调法，但是忽略了题目中的搜索树的条件。

思想

因为是搜索树，所以只有一条路径

1

法一：

/* 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} root* @return {boolean}*/
var isValidBST = function(root) {let arr = [];const buildArr = function(root) {if (root) {buildArr(root.left);arr.push(root.val);buildArr(root.right);}}buildArr(root);for (let i = 1; i < arr.length; ++i) {if (arr[i] <= arr[i - 1])return false;}return true;
};

第一想法

先序遍历，然后递归，写不出来，然后我又忽略了题意，即使按我的想法做出来，
也不符合题意：

有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

思想

• 有效二叉树的中序遍历出来是从小到大的，（迭代、回调）转换为数组，然后比较

法二：

let pre = null;
var isValidBST = function (root) {let pre = null;const inOrder = (root) => {if (root === null)return true;let left = inOrder(root.left); //左
// 中序遍历，验证遍历的元素是不是从小到大if (pre !== null && pre.val >= root.val)return false;pre = root;let right = inOrder(root.right);//右return left && right;}return inOrder(root);
};

思想

• 确定递归函数，返回值以及参数
  let pre = null; 用来记录前一个节点

• 确定终止条件
  如果是空节点 是不是二叉搜索树呢？
  是的，二叉搜索树也可以为空！
  代码如下：
  if (root == NULL) return true;

• 确定单层递归的逻辑
  中序遍历，一直更新maxVal，一旦发现maxVal >= root->val，就返回false，注意元素相同时候也要返回false。

回调法的过程：使用一个节点（pre）来记录之前访问过的节点，判断依据是当前节点的val一定要大于pre.val。