+
+
Posts List
  1. 83 删除排序链表中的重复元素
  2. 88 合并两个有序数组
  3. 100 相同的树
  4. 101 对称二叉树
  5. 104 二叉树的最大深度
  6. 107 二叉树的层次遍历 II

LeetCode上的「简单」题(四)

83 删除排序链表中的重复元素

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

1
2
输入: 1->1->2
输出: 1->2

示例 2:

1
2
输入: 1->1->2->3->3
输出: 1->2->3

解一:

使用递归。

1
2
3
4
5
6
7
8
var deleteDuplicates = function (head) {
if (!head||!head.next) return head;
else if(head.next.val===head.val) return deleteDuplicates(head.next);
else {
head.next = deleteDuplicates(head.next);
return head
}
};

解二:

使用循环。这里涉及JavaScript的「引用传递」,对cur的修改也会同步到head中。

1
2
3
4
5
6
7
8
var deleteDuplicates = function (head) {
var cur = head;
while(cur&&cur.next){
if (cur.next.val===cur.val) cur = cur.next;
else cur.next = cur.next.next
}
return head;
};

88 合并两个有序数组

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

说明:

  • 初始化nums1nums2的元素数量分别为mn
  • 你可以假设nums1有足够的空间(空间大小大于或等于m+n)来保存nums2中的元素。

示例:

1
2
3
4
5
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

解一:

数组拼接后sort排序。缺点是没有利用nums1nums2本身是有序数组的优势。

1
2
3
4
5
6
var merge = function(nums1, m, nums2, n) {
for (var i = 0;i<nums2.length;i++) nums1[m+i] = nums2[i];
nums1.sort(function (a,b) {
return a-b
})
};

解二:

插入排序,由于nums1num2均为有序数组,所以j不需要每次循环都复位。

1
2
3
4
5
6
7
8
var merge = function (nums1, m, nums2, n) {
var j = 0;//nums1的第j位
for (var i = 0; i < nums2.length; i++) {//nums2的第i位
while (!(nums2[i] < nums1[j] || j >= m + i)) j++;
for (var k = nums1.length - 1; k > j; k--) nums1[k] = nums1[k - 1];
nums1[j] = nums2[i];
}
};

⚠️坑:初始代码中有一句话:”@return {void} Do not return anything, modify nums1 in-place instead.”,注意其中的in-place,OJ不看return,只看nums1,这说明要在num1上做修改,并且类似concatslice之类的方法都无效。

100 相同的树

给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

1
2
3
4
5
6
7
输入:       1         1
/ \ / \
2 3 2 3

[1,2,3], [1,2,3]

输出: true

示例 2:

1
2
3
4
5
6
7
输入:      1          1
/ \
2 2

[1,2], [1,null,2]

输出: false

示例 3:

1
2
3
4
5
6
7
输入:       1         1
/ \ / \
2 1 1 2

[1,2,1], [1,1,2]

输出: false

解一:

先比较pqval,若相等则进一步判断pq左右节点是否相等。这种「进一步」运用了递归的思想。这道题要注意处理好「存在与否」的问题,因此我使用了数组cur来保存左右节点的值,若不存在则保存null,避免了.val的上一级是undefined的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var isSameTree = function (p, q) {
if (!p || !q) return p === q;
if (p.val === q.val) {
var cur = [];
cur[0] = p.left ? p.left.val : null;
cur[1] = q.left ? q.left.val : null;
cur[2] = p.right ? p.right.val : null;
cur[3] = q.right ? q.right.val : null;
if (cur[0] === cur[1] && cur[2] === cur[3]) {
if (cur[0] === null && cur[2] === null) return true;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
} else return false
} else return false
};

解二:

看了一下其他同学的题解,发现我是傻了,每次比较当前的val就好了,不需要再比较左右节点,因为下一次递归的时候还是会比较val的。

1
2
3
4
5
var isSameTree = function(p, q) {
if(p == null || q == null) return p===q;
if(p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

解三:

调试的时候总会console.log看一下pq的结构,于是我就想,直接用字符串比较岂不更好?

1
2
3
4
5
var isSameTree = function (p, q) {
p = JSON.stringify(p);
q = JSON.stringify(q);
return p===q
};

101 对称二叉树

错误的尝试:

在上一题的基础上写的,因为考虑到isSymmetric只接受一个参数,因此又自作聪明用了cur来保存左右节点的值。这样比较下来确保的并不是二叉树对称(整体对称),而是每个节点的左右节点值相等,也就是局部对称。

1
2
3
4
5
6
7
8
var isSymmetric = function(root) {
if (root===null) return true;
var cur = [];
cur[0] === root.left? root.left.val:null;
cur[1] === root.right? root.left.val:null;
if (cur[0]!==cur[1]) return false;
return isSymmetric(root.left)&&isSymmetric(root.right)
};

解:

看了官方解答,就像发现了新大陆一样,原来「对称」可以放到更大的格局,一个对称的物体必然和自身成镜像。所以可以给isSymmetric增加一个镜像参数。


1
2
3
4
5
var isSymmetric = function (p, q = p) {
if (p === null || q === null) return p === q;
if (p.val !== q.val) return false;
return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left)
};

参考资料:

104 二叉树的最大深度

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

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

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

示例:

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

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

返回它的最大深度 3 。

解:

递归。

1
2
3
4
var maxDepth = function(root) {
if (root===null) return 0;
return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
};

107 二叉树的层次遍历 II

给定一个二叉树,返回其节点值自底向上的层次遍历。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

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

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

返回其自底向上的层次遍历为:

1
2
3
4
5
[
[15,7],
[9,20],
[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
26
var levelOrderBottom = function (root) {
if (!root) return [];
var queue = [root];
var n = 0;
var ans = [];
if (root.val !== null) ans.push([root.val]);
while (queue.length) {
var arr = [];
var line = [];
while (queue.length) {
var curr = queue.shift();
if (curr.left) {
arr.push(curr.left);
line.push(curr.left.val);
}
if (curr.right) {
arr.push(curr.right);
line.push(curr.right.val)
}
}
n++;
queue = arr;
if (line.length) ans.unshift(line);
}
return ans
};

本文作者: rhinoc

本文链接: https://www.rhinoc.top/leetcode_4/

版权声明: 本博客所有文章除特别声明外,均采用BY-NC-SA 4.0国际许可协议,转载请注明。

打赏
Love U 3000
  • Through WeChat
  • Through Alipay