秋招复习计划-算法题5

  |  

前言

栈的压入、弹出序列,从上往下打印二叉树,二叉树的后续遍历,二叉树和为某一值的遍历序列,复杂链表的复制


38



栈的压入、弹出序列

题目描述

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出序列。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入需顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列

题目分析

首先我们判断一个弹出序列的标准就是它是否满足栈先进后出的特定。那么我们分析一下思路,对于这个题目我们需要引入一个辅助栈。我们将压入序列的第一个值,压入到辅助栈中,然后比较这是辅助栈栈顶的值和弹出序列的第一个值是否相等,相等就弹出辅助栈的值,移除弹出序列的第一个值,然后再判断,如果相等执行执行相同操作。如果不等,则压入压入序列的第二个值,循环比较。如果最后当压入序列的内容全部压入了,并且输出序列为空,说明我们的压入序列是可以按弹出序列弹出的,返回true。否则当压入序列空,而弹出序列没空,说明不能按序弹出,返回false。总体思路是这样的,具体可以在程序上做调整

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function IsPopOrder(pushV, popV) {
const helpStack = [];
let flag = false;
/*
这里说明一下为什么条件要带上helpStack.length,因为最后一次压入后,pushV.length就为0了,但是我 们还是需要进行最后一次判断
*/
while(pushV.length || helpStack.length) {
while(helpStack[helpStack.length - 1] === popV[0] && helpStack.length) {
helpStack.pop();
popV.shift();
}
if(!popV.length) {
flag = true;
}
if(!pushV.length) {
break;
}
helpStack.push(pushV.shift());
}
return flag;
}

同样的思路我们可以简化一下程序,我们先进行一次压入序列对辅助栈的压入,然后我们去取辅助栈的栈顶,和弹出序列的队列头,如果不等我们再退回,然后判断一下压入序列是否全部压入了,如果全部压入了,那么说明压入序列和弹出序列无法匹配。如果还没有全部压入,则继续压入。如果相等,不需要任何操作,直接进行下一次循环,这样我们就能将二次循环的程序优化到一次循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function IsPopOrder(pushV, popV) {
const helpStack = [];
helpStack.push(pushV.shift());
while(helpStack.length) {
const x = helpStack.pop(),
y = popV.shift();
if(x !== y) {
helpStack.push(x);
popV.unshift(y);
if(!pushV.length) {
return false;
}
helpStack.push(pushV.shift());
}
}
return true;
}

从上往下打印二叉树

题目描述

从上往下打印二叉树的每个节点,同层节点从左至右打印

题目分析

这其实就是树的广度遍历。树的广度遍历我们一般采用遍历队列的方式,利用队列先进先出的特点。

先将树的根节点输入到队列中,然后取出,将节点的左子树节点输入到队列,再将右子树输入到队列中,这样就可以遍历每一层。且输出的结果也满足从左往右。

总的来说这道题还是很简单的

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function PrintFromTopToBottom(root) {
const queue = [],
res = [];
if(root === null) {
return res;
}
queue.push(root);
while(queue.length) {
const pRoot = queue.shift();
if(pRoot.left !== null) {
queue.push(pRoot.left);
}
if(pRoot.right !== null) {
queue.push(pRoot.right);
}
res.push(pRoot.val);
}
return res;
}

生成完全二叉树的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}
function createTree(n) {
if (n === 1) {
return new TreeNode(1);
}
const root = new TreeNode(n);
root.left = createTree(n - 1);
root.right = createTree(n - 1);
return root;
}
const tree = createTree(4);

二叉搜索树的后续遍历序列

题目描述

输入一个整数数组,判断该数组是不是某二叉搜索树的后续遍历结果,如果是返回true,不是返回false,假设输入的数组的任何一个值都不相同。

题目分析

首先我们要知道一个二叉搜索树的特点,及它的左节点<根节点<右节点,通过这个特性,我们就能判断一个数组是否为一个二叉搜索树的后续遍历序列了。

  • 首先,我们获得数组最后的根节点
  • 通过根节点我们可以判断出数组中那部分是左子树,那部分是右子树
  • 判断左子树中的每个值是否都小于r,右子树中的每个值是否都大于r。
  • 对左、右子树进行递归

这道题我们以用递归,也可以用循环。不得不说,这道题能用循环写出来是真的厉害

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function VerifySquenceOfBST(sequence) {
if(!sequence.length) return false;
return judge(sequence, 0, sequence.length - 1);
}

function judge(a, l, r) {
if(l >= r) return true; //当遍历完毕,l=r,返回true
let i = r;
while(a[i - 1] > a[r] && i > 1) i--; //找到左子树的根节点
for(let j = i - 1; j >= 1; j--) {
if(a[j] > a[r]) return false;
/*
判断左子树是否都比根节点小,为什么不比较右子树和根节点,
因为前面找寻左子树根节点时,已经默认右子树比根节点都大了
*/
}
return judge(a, l, i - 1) && judge(a, i, r - 1); //递归
}

递归的版本没什么好讲的,比较常规

1
2
3
4
5
6
7
8
9
10
11
12
function VerifySquenceOfBST(sequence) {
let n = sequence.length - 1;
let i = 0;
if(!n) return false;
while(n--) {
while(sequence[i] < sequence[n]) i++; //判断左子树是否都比根节点小
while(sequence[i] > sequence[n]) i++; //判断右子树是否都比根节点大
if(i<n) return false; //如果符合要求,n最后会遍历到整个数组尾
i = 0;
}
return true;
}

非递归版本不得不说写的十分精妙,它巧妙的利用了二叉搜索树的特点,但是这样的循环有一点冗余,因为它在判断右子树的时候,整个左子树一直在遍历,但是由于左子树比右子树小的特定,所以如果它的确是一个二叉搜索树的后续遍历序列,那么并不会对判断造成影响。

二叉树中和为某一值的路径

题目描述

输入一颗二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。路径定义为从树的根节点开始往下一直到叶节点所经过的节点形成一条路径

题目分析

这道题目思路很清晰,而且由于对路径的定义是根节点到叶节点,所以题目也很简单。就是二叉树的深度遍历,当到达叶节点后,如果和不与期望值相等,就回退。

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function FindPath(root, expetNumber) {
const list = [],
listAll = [];
return findpath(root, expetNumber, list, listAll);
}

function findpath(root, expetNumber, list, listAll) {
if(root === null) return listAll;
list.push(root.val);
if(root.left === null && root.right === null && x === 0) {
listAll.push(Array.of(...list));//当到达叶节点的时候判断和,相当,将当前路径输入到listAll中
}
findpath(root.left, x, list, listAll);
findpath(root.right, x, list, listAll);
list.pop(); //当递归到叶节点后,不管相不相等,开始回退
return listAll;
}

复杂链表的复制

题目描述

输入一个复杂链表(每个节点中有节点值,还有两个指针,一个指针指向下一个节点,一个指针指向任意一个节点),返回结果为复制后复杂链表的head。

题目分析

大佬说这道题有三种解法,那么就有三种解法

解法一:

普通解法,先复制节点,并用p.next连接起来,这个过程需要的时间是O(n)。然后再去设置p.random,这个过程需要先遍历一遍p链表,然后再复制p.random的时候,需要再遍历一遍p去找,所以需要的时间复杂度是O(n^2)

解法二:

这个解法我们使用ES6的新数据结构Map。Map的键值和键名都可以是任意类型,所以我们这样就可以早每个p节点和p’节点间建立对应关系,这样我们在复制p.random的时候就可以直接使用对应关系复制,将时间复杂度讲到O(n),这是个典型的空间换时间的优化

解法三:

解法三不再使用map来建立对应关系,而是破坏原链表的结构,将p.next指向p’。这样再复制p.random时,让pNode.next(也就是pNode’)的random指向pNode.random.next。再复制完成后,再恢复原链表结构。总的来说,虽然节省了空间,也把时间复杂度降到了O(n),但是过于复杂了

算法代码

解法二代码:

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
29
30
31
32
function RandomListNode(x) {
this.label = x;
this.next = null;
this.random = null;
}

function Clone(pHead) {
if(pHead === null) {
return null;
}
const map = new Map();
let p, p2;
p = pHead;
p2 = new RandomListNode(pHead.label);
const pHead2 = p2;
map.set(p, p2);
while(p) {
if(p.next) p2.next = new RandomListNode(p.next.lable); //复制节点,next相连
else p2.next = null;
p = p.next;
p2 = p2.next;
map.set(p, p2);
}
p = pHead;
p2 = pHead2;
while(p !== null) {
p2.random = map.get(p.random);//获得p.random指向的p节点的对应p'节点
p = p.next;
p2 = p2.next;
}
return pHead2;
}

解法三代码:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
function RandomListNode(x) {
this.label = x;
this.next = null;
this.random = null;
}

function Clone2(pHead) {
cloneNodes(pHead);
connectRandom(pHead);
return reconnectNodes(pHead);
}

function cloneNdoes(pHead){
while(pNode !== null) {
const newNode = new RandomListNode(pNode.lable); //复制节点
newNode.next = pNode.next;
pNode.next = newNode;
/*
破坏原链表,建立指向关系,现在形成的关系是
pNode.next -> newNode, newNode.next -> 下一个pNode
*/
pNode = newNode.next;
}
}
function connectRandom(pHead) {
let pNdoe = pHead;
while(pNode !== null) {
if(pNode.random !== null) {
pNode.next.random = pNode.random.next;
// newNode.random = pNode.random.next(另一个newNode),复制随机节点
}
pNode = pNode.next.next; // newNode.next
}
}

function reconnectNdoes(pHead) {
let pNode = pHead;
let newNodeHead = null,
newNode = null;
if(pNode !== null) {
newNodeHead = newNode = pNode.next; //新链表的头节点复制
pNode.next = newNode.next; //恢复原链表结构
pNode = newNode.next; //p指向下一个p
}
while(pNode !== null){
newNode.next = pNode.next;
/*
由于pNode比newNode后一个位置,所以pNode.next就是下一个
newNode,将新链表连接起来
*/
newNode = newNdoe.next;
pNode.next = newNode.next;//恢复原链表结构
pNode = pNode.next;
}
return newNodeHead;
}
文章目录
  1. 1. 栈的压入、弹出序列
    1. 1.0.1. 题目描述
    2. 1.0.2. 题目分析
    3. 1.0.3. 算法代码
  • 2. 从上往下打印二叉树
    1. 2.0.1. 题目描述
    2. 2.0.2. 题目分析
    3. 2.0.3. 算法代码
  • 3. 二叉搜索树的后续遍历序列
    1. 3.0.1. 题目描述
    2. 3.0.2. 题目分析
    3. 3.0.3. 算法代码
  • 4. 二叉树中和为某一值的路径
    1. 4.0.1. 题目描述
    2. 4.0.2. 题目分析
    3. 4.0.3. 算法代码
  • 5. 复杂链表的复制
    1. 5.0.1. 题目描述
    2. 5.0.2. 题目分析
    3. 5.0.3. 算法代码
  • |