佳宸学习和分享笔记的地方

0%

leetcode树 算法基础

leetcode树 算法基础

二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回它的最大深度 3 。

解:递归遍历左右子树,每层+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if(!root) return 0
const left = maxDepth(root.left)
const right = maxDepth(root.right)
return Math.max(left, right) + 1
};

验证二叉搜索树

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

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

示例 1:

1
2
3
4
5
输入:
2
/ \
1 3
输出: true

解答:之前理解错了,不是当前节点满足就行,子节点的所有祖先节点都要满足。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function(root, pre = null, next = null) {
if (!root) return true
// 先序遍历 以及哪些上下限进行了比较
// sole.log(root && root.val, pre && pre.val, next && next.val);
if (pre && pre.val >= root.val) return false
if (next && next.val <= root.val) return false
// 逻辑判断 递归 如果左边true就是遍历倒底了 则返回右边
// !关键递归 如果是左子节点把当前节点作为下限 右子节点把当前节点作为上限
return isValidBST(root.left, pre, root) && isValidBST(root.right, root, next);
};

对称二叉树

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

1
2
3
4
5
    1
/ \
2 2
/ \ / \
3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
2
3
4
5
  1
/ \
2 2
\ \
3 3

解答:还是递归,左右镜像判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
// 如果是空树直接返回
if (root === null) return true
return isMirror(root.left, root.right)
};

function isMirror(left, right) {
// 如果两子都为空,返回真
if(left === null && right ===null) return true
// 有一边为空,则不对称
if(left === null || right ===null) return false
// 条件判断 左边的子左边与右边的子右边相等
return left.val === right.val && isMirror(left.left, right.right) && isMirror(left.right, right.left)
}

二叉树的层次遍历

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

1
2
3
4
5
[
[3],
[9,20],
[15,7]
]

解答: 打印root树仔细查看它的结构,迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (!root) return []
let res = [], queue = [root]
while(queue.length) {
// 每层的子节点数
let level = queue.length
let current = []
while(level--) {
let node = queue.shift()
current.push(node.val)
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
}
res.push(current)
}
return res
};

将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

1
2
3
4
5
6
7
8
9
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

0
/ \
-3 9
/ /
-10 5

解答:要明确两个点,1.二叉搜索树左子树小右子树大,高度要平衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
if(!nums.length) return null
let middleL = nums.length >> 1
// 每次取到中间数
let node = new TreeNode(nums[middleL])
// 递归,左边左树,右边右数
node.left = sortedArrayToBST(nums.slice(0, middleL))
node.right = sortedArrayToBST(nums.slice(middleL + 1))
return node
};

希望能步入学习正轨,看同届前端群的好几位大哥进腾讯阿里提前批就上岸了。自己不能越差越远啊