概念
链式存储
1. 先序遍历
2.1 递归解法
解题思路
代码
preorder_recur(node) {if (!node) {node = this.root}console.log(node.data)this.preorder_recur(node.left)this.preorder_recur(node.right)}
1.2 非递归解法
解题思路
代码
preorder(node) {if (!node) {node = this.root}let stack = []let res = []stack.push(node)if (node === null) {return []}while (stack.length > 0) {let node = stack.pop()res.push(node.val)if (node.right) {stack.push(node.right)}if (node.left) {stack.push(node.left)}}return res}
2. 中序遍历
2.1 递归解法
if (!node) {node = this.root}this.preorder_recur(node.left)console.log(node.data)this.preorder_recur(node.right)
2.2 非递归解法
inorder(node) {if (!node) {node = this.root}let stack = []let res = []if (node === null) {return []}while (node !== null || stack.length > 0) {while (node !== null) {stack.push(node)node = node.left}node = stack.pop()res.push(node.data)node = node.right}}
3. 后序遍历
3.1 递归解法
postorder_recur(node) {if (!node) {node = this.root}this.preorder_recur(node.left)this.preorder_recur(node.right)console.log(node.data)}
3.2 非递归解法
postorder(node) {if (!node) {node = this.root}let stack = []let res = []if (node === null) {return []}stack.push(node)while (stack.length > 0) {let node = stack.pop()res.unshift(node.val)if (node.left) {stack.push(node.left)}if (node.right) {stack.push(node.right)}}}
4. 层序遍历
levelOrder(root) {let nodequeue = []let res = []if (root === null) {return []}nodequeue.push(root)let level = 0while (nodequeue.length > 0) {res[level] = []let len = nodequeue.lengthfor (let i = 0; i < len; i++) {let node = nodequeue.shift()res[level].push(node.val)if (node.left) {nodequeue.push(node.left)}if (node.right) {nodequeue.push(node.right)}}level++}}
5. 路径查找
binaryTreePaths(root) {let nodestack = []let res = []let pathstack = []if (root === null) {return res}nodestack.push(root)pathstack.push(root.val.toString())while (nodestack.length > 0) {let node = nodestack.pop()let path = pathstack.pop()if (node.left === null && node.right === null) {res.unshift(path)}if (node.left) {nodestack.push(node.left)pathstack.push(path + '->' + node.left.val)}if (node.right) {nodestack.push(node.right)pathstack.push(path + '->' + node.right.val)}}return res}
