【JavaScript】前端算法题（重建二叉树、反向输出链表每个节点）

苏小咪

前言

今天复习了一些前端算法题，写到一两道比较有意思的题：重建二叉树、反向输出链表每个节点
题目

重建二叉树: 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路

前序遍历(根左右)和中序遍历（左根右）

思路就是使用递归把他分化为每个小的二叉树，然后都根据前序遍历(根左右)和中序遍历（左根右）的特性，前序的首元素就是根，然后再找到中序的根，根的左边就是左右边就是右，再进行递归，直到前序为null的时候就代表没有根节点了，那这个元素就是尾节点

一.
①[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]-> val=>1 ->L([2,4,7],[4,7,2]) & R([3,5,6,8],[5,3,8,6])    根节点 1 ,有左右节点

二.
①L([2,4,7],[4,7,2])->  val=>2  ->L([4,7],[4,7]) && R(null , null)     根节点2(属1的左节点) ,有左节点,无右节点
②R([3,5,6,8],[5,3,8,6])->  val=>3  ->L([5],[5]) && R([6,8],[6,8])     根节点3(属1的右节点) ,有左右节点

三.
①L([4,7],[4,7])  ->val=>4 -> L(null , null) && R([7],[7])             根节点4(属2的左节点) ,有右节点,无左节点
②R([6,8],[8,6]) -> val=>6 -> L([8] , [8])  && R(null , null)          根节点6(属3的右节点),有左节点,无右节点
③L([5],[5]) -> val=>5->(null,null)->终止                              尾节点5(属3的左节点)

四.
①R([7],[7]) -> val=>7 ->终止                                          尾节点7(属4的右节点)
②L([8],[8]) -> val=>8 ->终止                                          尾节点8(属6的左节点)

代码实现

1. function rebuildBinaryTree(front, centre) {
2.     //判断是否为空节点
3.     if (!front || front.length == 0) {
4.         return null;
5.     }
6.     // 根节点
7.     var TreeNode = {
8.         val: front[0]
9.     };
10.     for (var i = 0; i < front.length; i++) {
11.         //找到中序遍历根节点位置
12.         if (centre[i] === front[0]) {
13.             //中序遍历(左根右)
14.             //根节点左边的节点为该节点的左边
15.             TreeNode.left = rebuildBinaryTree(front.slice(1, i + 1), centre.slice(0, i));
16.             //根节点右边的节点为该节点的右边
17.             TreeNode.right = rebuildBinaryTree(front.slice(i + 1), centre.slice(i + 1));
18.         }
19.     }
20.     return TreeNode;
21. }
22. let tree = rebuildBinaryTree([1, 2, 4, 7, 3, 5, 6, 8], [4, 7, 2, 1, 5, 3, 8, 6])
23. console.log(tree)

复制代码

题目

从尾到头打印链表: 输入一个链表，从尾到头打印链表每个节点的值。

思路

由于链表是单向的，我们不能直接从头节点开始反向遍历。
所以可以使用数组来模拟栈。迭代遍历链表，将链表每个节点压入栈中，然后再依次从栈中弹出并打印。

代码实现

1. // 定义一个节点类，结构data表示节点数据、next表示下个节点的指针
2. class Node {
3.     constructor(data) {
4.         this.data = data
5.         this.next = null
6.     }
7. }
9. function printNode(node) {
10.     // 定义一个数组表示模拟栈
11.     let stack = new Array()
12.     // 初始化当前节点为传入的节点
13.     let NodeNextElm = node
14.     //判断下个节点指针是否为空
15.     while (NodeNextElm !== null) {
16.         //压栈
17.         stack.push(NodeNextElm.data)
18.         //存储下个节点的指针
19.         NodeNextElm = NodeNextElm.next
20.     }
21.     while (stock.length > 0) {
22.         //当栈不为空时，循环弹出栈顶元素并打印
23.         console.log(stack.pop())
24.     }
25. }
26. //初始化链表
27. //新建链表节点
28. const node1 = new Node(1)
29. const node2 = new Node(2)
30. const node3 = new Node(3)
31. //手动存储下个节点的指针
32. node1.next = node2
33. node2.next = node3
34. //调用
35. printNode(node1)

复制代码

过程解析

1. 一. 进入，此时的NodeNextElm：{
2.     "data": 1,
3.     "next": {
4.         "data": 2,
5.         "next": {
6.             "data": 3,
7.             "next": null
8.         }
9.     }
10. }
12. 此时进入while循环：
14. ①第一次循环：
16. 栈stack：[1]
18. NodeNextElm:{
19.         "data": 2,
20.         "next": {
21.                 "data": 3,
22.                 "next": null
23.         }
24. }
26. ②第二次循环：
28. 栈stack：[1,2]
30. NodeNextElm:{
31.         "data": 3,
32.         "next": null
33. }
35. ③第三次循环：
37. 栈stack：[1,2,3]
39. NodeNextElm:null
41. 循环结束
43. pop()弹出栈并打印：3，2，1

复制代码

上述为个人整理内容，水平有限，如有错误之处，望各位园友不吝赐教！如果觉得不错，请点个赞和关注支持一下！谢谢~๑•́₃•̀๑ [鲜花][鲜花][鲜花]

来源:https://www.cnblogs.com/nothavebug/p/18331362
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！