二叉树面试题

我之前面试了好几家公司,都会考一些关于二叉树的面试题,比如下面这几个面试题:

  1. 二叉树有哪几种遍历方式
  2. 不用递归如何遍历二叉树
  3. 如何判断二叉树是对称二叉树
  4. 将二叉树左右节点翻转
  5. 实现一个函数接收任意二叉树,求二叉树所有根节点到叶子路径组成的数字之和

前端常考的算法题就是二叉树和排序了,这些好像很多公司都会有一两道这样的题目,大家面试前可以重点看一下这些知识点,这篇文章主要讲解二叉树。

基础知识

了解二叉树之前我们先要知道什么是二叉树和二叉树的组成。

二叉树是每个节点不超过两个。一棵最上面的节点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,它下面的节点称为子节点,一个节点可以有0个或多个子节点,没有任何子节点的节点称为叶子节点

下面代码就是创建二叉树的过程。

functionNode(value, left, right) {

this.value = value;

this.left = left;

this.right = right;

}

functionBST() {

this.root = null;

this.insert = insert;

}

functioninsert(value) {

let node = new Node(value, null, null)

if (this.root == null) {

// 根节点

this.root = node;

} else {

// 子节点

let current = this.root;

let parent;

while (true) {

parent = current;

if (value < current.value) {

current = current.left;

if (current == null) {

parent.left = node;

break;

}

} else {

current = current.right;

if(current == null) {

parent.right = node;

break;

}

}

}

}

}

let tree = new BST()

tree.insert(1)

tree.insert(2)

tree.insert(3)

tree.insert(4)

console.log(tree.root)

复制代码

insert 方法是向二叉树中出入一个节点,我们需要判断节点的位置,分别对比左右节点的大小关系,然后选择性的输入到其中。

实战题目

文章的开头有5道面试题,下面开始做题啦!

问:二叉树有哪几种遍历方式?

答:有三种遍历方式,中序,先序,后序。中序遍历按照节点上的键值,以升序访问二叉树上的所有节点。先序遍历先访问根节点,然后以同样方式访问左子树和右子树。后序遍历先访问叶子节点,从左子树到右子树,再到根节点。

下图是中序遍历的路径图,10->22->30->56->77->81->92(按照升序访问的规则)

关于二叉树的面试题

// 中序遍历

functioninOrder(node) {

let result = []

if (!(node == null)) {

inOrder(node.left)

result.push(node.value)

inOrder(node.right)

}

return result

}

let tree = new BST()

tree.insert(56)

tree.insert(22)

tree.insert(81)

tree.insert(10)

tree.insert(30)

tree.insert(77)

tree.insert(92)

inOrder(tree.root)

复制代码

下图是先序遍历的路径图,50->10->5->15->70->60->80(按照先根节点再子节点)

关于二叉树的面试题

// 先序遍历

functionpreOrder(node) {

let result = []

if (!(node == null)) {

result.push(node.value)

preOrder(node.left)

preOrder(node.right)

}

return result

}

let tree = new BST()

tree.insert(50)

tree.insert(10)

tree.insert(70)

tree.insert(5)

tree.insert(15)

tree.insert(60)

tree.insert(80)

preOrder(tree.root)

复制代码

下图是后序遍历的路径图,3->22->16->37->99->45->23(按照先子节点再根节点)

关于二叉树的面试题

// 后序遍历

functionpostOrder(node) {

let result = []

if (!(node == null)) {

postOrder(node.left)

postOrder(node.right)

result.push(node.value)

}

return result

}

let tree = new BST()

tree.insert(23)

tree.insert(16)

tree.insert(45)

tree.insert(3)

tree.insert(22)

tree.insert(37)

tree.insert(99)

postOrder(tree.root)

复制代码

问:不用递归如何遍历二叉树?

其实代码中的 insert 方法就是没有使递归而是使用 while 循环进行遍历的,不知道你注意到了没有。下面我再通过使用 while 实现遍历。

使用循环遍历二叉树还必须使用栈进行回溯算法。

// 中序遍历

functioninOrder(node) {

let stack = []

let result = []

let parent = node;

while (parent !== null || stack.length) {

if (parent !== null) {

stack.push(parent)

parent = parent.left

} else {

parent = stack.pop()

result.push(parent.value)

parent = parent.right

}

}

console.log(result)

}

复制代码

// 先序遍历

functionpreOrder(node) {

let stack = []

stack.push(node)

let result = []

while (stack.length !== 0) {

let parent = stack.pop()

if (parent.right !== null) {

stack.push(parent.right)

}

if (parent.left !== null) {

stack.push(parent.left)

}

result.push(parent.value)

}

console.log(result)

}

复制代码

// 后序遍历

functionpostOrder(node) {

let stack = []

stack.push(node)

let result = []

let parent = node

while (stack.length !== 0) {

parent = stack.pop()

if (parent.left !== null) {

stack.push(parent.left)

}

if (parent.right !== null) {

stack.push(parent.right)

}

result.unshift(parent.value)

}

console.log(result)

}

复制代码

这里有一篇文章《非递归实现二叉树先序、中序和后序遍历》讲解了代码实现的思路。但是是Java代码写的,哈哈!

如果你对栈数据结构不了解,可以阅读我之前写的一篇文章《关于JS括号匹配的面试题》。

关于二叉树的面试题

总结

先序:根左右,

中序:左根右,

后续:左右根。

这里在提一句,深度优先和广度优先的感念,

“深度优先搜索就是树的先序遍历”,“广度优先搜索就是树的按层遍历”。

关于二叉树的面试题

深度优先,先序遍历 ABEFGCD

广度优先,按层遍历 ABCDEFG

问:如何判断二叉树是对称二叉树

如果一个树的左子树与右子树镜像对称,那么这个树是对称的。

关于二叉树的面试题

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

var node1 = {

value: 1,

left: {

value: 2,

left: {

value: 3

},

right: {

value: 4

}

},

right: {

value: 2,

left: {

value: 4

},

right: {

value: 3

}

}

}

复制代码

递归

functionisSymmetric (root) {

return isMirror(root, root)

}

functionisMirror (t1, t2) {

if (t1 == null && t2 == null) returntrue;

if (t1 == null || t2 == null) returnfalse;

return (t1.value === t2.value) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right)

}

console.log(isSymmetric(node1))

复制代码

问:将二叉树左右节点翻转

关于二叉树的面试题

关于二叉树的面试题

原题:二叉树的数据结构如下,需要将二叉树各节点左右翻转

var node1 = {

value: 1,

left: {

value: 2,

left: {

value: 4

},

right: {

value: 5

}

},

right: {

value: 3,

left: {

value: 6

},

right: {

value: 7

}

}

}

复制代码

思路:

  1. 先将左右节点交换位置
  2. 再递归子节点

functionreverse(node) {

if (node != null) {

let temp = node.left;

node.left = node.right;

node.right = temp;

reverse(node.left);

reverse(node.right);

}

}

复制代码

偷偷告诉你,这个题目是滴滴的面试题,感觉还挺难的!哈哈。

5、实现一个函数接收任意二叉树,求二叉树所有根节点到叶子路径组成的数字之和

functiongetPathSum(root) {

let total = 0

functionnext(node) {

if (node != undefined) {

total += node.value

next(node.left)

next(node.right)

}

}

next(root)

return total

}

复制代码

就是使用先序遍历完成

6、二叉树定义如下,实现函数 getPathSum(node)返回7=(1+2)+(1+3)

var node = {

value: 1,

left: {

value: 2,

left: null,

right: null

},

right: {

value: 3,

left: null,

right: null

}

}

复制代码

按照先序遍历

functiongetPathSum(root) {

let total = 0

let left = []

let right = []

functionnext(node, flag) {

if (node != undefined) {

if (flag === 0) {

left.push(node.value)

right.push(node.value)

total = node.value + node.value

}

if (flag === 1) {

left.push(node.value)

total += node.value

}

if (flag === 2) {

total += node.value

right.push(node.value)

}

next(node.left, 1)

next(node.right, 2)

}

}

next(root, 0)

return`${total}=(${left.join('+')})+(${right.join('+')})`

}

复制代码

这些就是我最近面试的一些题目,大家感觉怎么样?

哪里有问题,欢迎留言指正。

以上是 二叉树面试题 的全部内容, 来源链接: www.h5w3.com/115383.html

回到顶部