# 二叉树面试题

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

## 基础知识

``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` 方法是向二叉树中出入一个节点，我们需要判断节点的位置，分别对比左右节点的大小关系，然后选择性的输入到其中。

## 实战题目

### 问：二叉树有哪几种遍历方式？

``// 中序遍历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)``复制代码``

``// 先序遍历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)``复制代码``

``// 后序遍历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)``复制代码``

### 问：不用递归如何遍历二叉树？

``// 中序遍历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 = nodewhile (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)}``复制代码``

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

### 问：如何判断二叉树是对称二叉树

``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 = 0functionnext(node) {if (node != undefined) {total += node.valuenext(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 = 0let 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.valueright.push(node.value)}next(node.left, 1)next(node.right, 2)}}next(root, 0)return`\${total}=(\${left.join('+')})+(\${right.join('+')})`}``复制代码``