树
是一种经常用到的数据结构,用来模拟具有树状结构性质的数据集合。
树里的每一个节点有一个根植和一个包含所有子节点的列表。从图的观点来看,树也可视为一个拥有 N
个节点和 N-1
条边的一个有向无环图。
二叉树
是一种更为典型的树状结构。如它名字所描述的那样,二叉树是每个节点最多有两个子树
的树结构,通常子树被称作“左子树”和“右子树”。
概念
- 前序遍历:前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树
- 中序遍历:中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树
- 后序遍历:后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点
- 递归和迭代
所谓前、中、后,不过是根的顺序,即也可以称为先根遍历、中根遍历、后根遍历
举个例子:
前序遍历为:F B A D C E G I H
中序遍历为:A B C D E F G H I
后序遍历为:A C E D B H I G F
二叉树的前序遍历
递归解法
思路:根据根、左、右的顺序遍历即可
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = root => {
return root ? [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)] : []
}
迭代解法
思路:利用栈来记录遍历的过程,实际上,递归就使用了调用栈,所以这里我们可以使用栈来模拟递归的过程
- 首先根入栈
- 将根节点出栈,将根节点值放入结果数组中
- 然后遍历左子树、右子树,因为栈是先入后出,所以,我们先右子树入栈,然后左子树入栈
- 继续出栈(左子树被出栈)…….
- 依次循环出栈遍历入栈,直到栈为空,遍历完成
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
const list = []
const stack = []
root && stack.push(root)
while(stack.length > 0) {
const popNode = stack.pop()
list.push(popNode.val)
popNode.right && stack.push(popNode.right)
popNode.left && stack.push(popNode.left)
}
return list
};
二叉树的中序遍历
递归解法
思路:左-跟-右
var inorderTraversal = root => {
return root ? [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)] : []
}
迭代解法
思路:
- 首先按从上到下的顺序左子树入栈,则栈的最顶层为最小的左孩子
- 取顶层的值,加入数组
- 取跟(上一层)加入数组
- 取右孩子加入数组
这里比较明显的感觉到了DFS
的思想
var inorderTraversal = root => {
let list = [], stack = []
while(root || stack.length) {
while(root) {
stack.push(root)
root = root.left
}
root = stack.pop()
list.push(root.val)
root = root.right
}
return list
}