网站开发python,小米发布会完整版,c2c的含义分别是什么,免费网站建设社区文章目录 51 验证二叉搜索树52 二叉搜索树中第k小的元素53 二叉树的右视图54 二叉树展开为链表55 从前序与中序遍历序列构造二叉树 51 验证二叉搜索树 递归对二叉搜索树进行中序遍历#xff0c;输出节点的值是单调递增的。方法1#xff1a;对二叉树进行中序遍历#xff0c;将… 文章目录 51 验证二叉搜索树52 二叉搜索树中第k小的元素53 二叉树的右视图54 二叉树展开为链表55 从前序与中序遍历序列构造二叉树 51 验证二叉搜索树 递归对二叉搜索树进行中序遍历输出节点的值是单调递增的。方法1对二叉树进行中序遍历将节点的值放入数组中判断数组是否单调递增双指针。方法2maxval记录前一个节点的数值初始化为一个绩效的值。方法3新建节点prepre指向前一个结点初始化为null。这里给出方法3的代码。
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? 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 (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? 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 (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? 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 (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? 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 (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? 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);
};
