【JavaScript】LeetCode：51-55

文章目录

51 验证二叉搜索树
52 二叉搜索树中第k小的元素
53 二叉树的右视图
54 二叉树展开为链表
55 从前序与中序遍历序列构造二叉树

51 验证二叉搜索树

在这里插入图片描述

递归
对二叉搜索树进行中序遍历，输出节点的值是单调递增的。
方法1：对二叉树进行中序遍历，将节点的值放入数组中，判断数组是否单调递增（双指针）。
方法2：maxval记录前一个节点的数值，初始化为一个绩效的值。
方法3：新建节点pre，pre指向前一个结点，初始化为null。这里给出方法3的代码。

/*** 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 pre = new TreeNode();pre = null;var isValid = function(root) {if(root == null){ // 空树也是二叉搜索树return true;}let left = isValid(root.left);if(pre != null && pre.val >= root.val){return false;}pre = root;let right = isValid(root.right);return left && right;}return isValid(root);
};

52 二叉搜索树中第k小的元素

在这里插入图片描述

递归
求中序遍历的第k个节点。
对二叉搜索树进行中序遍历，遍历到第k个节点时，记录结果res，记录结果后返回。

/*** 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} k* @return {number}*/
var kthSmallest = function(root, k) {var traversal = function(root){if(root == null){return;}traversal(root.left);if(k == 0){return;}if(--k == 0){res = root.val;}traversal(root.right);}let res = 0;traversal(root);return res;
};

53 二叉树的右视图

在这里插入图片描述

递归
先递归右子树，再递归左子树。
每层设置一个深度deep，遍历过程中，若该节点对应层的deep首次访问，则将该节点存入右视图结果数组中。

/*** 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 {number[]}*/
var rightSideView = function(root) {var traversal = function(root, deep){if(root == null){return;}if(deep == res.length){res.push(root.val);}traversal(root.right, deep + 1);traversal(root.left, deep + 1);}let deep = 0;let res = [];traversal(root, deep);return res;
};

54 二叉树展开为链表

在这里插入图片描述

递归
使用"倒"中序遍历，即右 -> 左 -> 中，遍历结果（654321）中的第一个节点就是链表的最后一个节点（6）。
新建pre作为前一个结点，初始化为null，随着"倒"中序遍历不断为其赋值为前一个结点。
除了最后一个节点的左节点不为null外，其他节点的左节点都为null，右节点都为pre。

/*** 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 {void} Do not return anything, modify root in-place instead.*/
var flatten = function(root) {var traversal = function(root){if(root == null){return;}traversal(root.right);traversal(root.left);if(pre != null){root.right = pre;root.left = null;}pre = root;}let pre = new TreeNode();pre = null;traversal(root);return root;
};

55 从前序与中序遍历序列构造二叉树

在这里插入图片描述

递归
前序数组的第一个元素为节点元素，在中序数组中寻找该元素作为分割点index，分割出左中序数组和右中序数组。
index可以理解为，在中序数组中，索引为index的位置前有index个元素，而左前序数组和左中序数组的length应该相等（右同理），因此可以借助index分割前序数组。
根据index分割前序数组，得到左前序数组和右前序数组。
叶子节点直接返回该节点，不必将左、右节点设置为null。
将左前序数组和右中序遍历继续遍历，右前序数组和右中序数组继续遍历。

/*** 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[]} preorder* @param {number[]} inorder* @return {TreeNode}*/
var buildTree = function(preorder, inorder) {var traversal = function(preorder, inorder){if(preorder.length == 0){return null;}let nodevalue = preorder[0];let node = new TreeNode(nodevalue);if(preorder.length == 1){ // 叶子节点直接返回return node;}let index = inorder.findIndex(item => item == node.val);let inleft = inorder.slice(0, index);let inright = inorder.slice(index + 1, inorder.length);let preleft = preorder.slice(1, 1 + index);let preright = preorder.slice(1 + index, preorder.length);node.left = buildTree(preleft, inleft);node.right = buildTree(preright, inright);return node;        }return traversal(preorder, inorder);
};