二叉树的遍历方式
- 深度优先遍历
- 前序遍历：根、左、右（递归法、迭代法）
- 中序遍历：左、根、右（递归法、迭代法）
- 后序遍历：左、右、根（递归法、迭代法）
举例：image.png
前序遍历：5、4、1、2、6、7、8
中序遍历：1、4、2、5、7、6、8
后序遍历：1、2、4、7、8、6、5
- 广度优先遍历
- 层次遍历（迭代法）
二叉树的存储方式
二叉树可以链式存储，也可以顺序存储
- 链式存储：利用指针，通过指针把分布在各个地址的节点串联起来
- 顺序存储：利用数组，存储的元素在内存是连续分布的
用上图二叉树举例说明一下顺序存储
如果父节点的数组下标是，那么左节点的数组下标是 i * 2+1，右节点的数组下标是 i * 2+2。
image.png
144. 二叉树的前序遍历
递归实现
var preorderTraversal = function(root) {
let res = [];
var traversal = function(cur) {
if (cur === null) {
return
}
res.push(cur.val)
traversal(cur.left)
traversal(cur.right)
}
traversal(root)
return res;
};
迭代实现
- 由于前序遍历是先根，后左右节点。所以优先存储根节点，再依次存储右节点、左节点，将左节点放在后面，这样在弹出节点时的顺序才会是先左节点，再右节点。
var preorderTraversal = function(root) {
if (!root) return []
let res = [];
let stack = [];
stack.push(root)
while(stack.length) {
let cur = stack.pop()
res.push(cur.val)
if (cur.right) {
stack.push(cur.right)
}
if (cur.left) {
stack.push(cur.left)
}
}
return res;
};
94. 二叉树的中序遍历
递归实现
var inorderTraversal = function(root) {
let res = [];
var traversal = function(root) {
if (root === null) {
return
}
traversal(root.left);
res.push(root.val)
traversal(root.right);
}
traversal(root)
return res;
};
迭代实现
- 与前序遍历不同，中序遍历需要优先拿到左节点。
- 先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进结果数组中）。
var inorderTraversal = function(root) {
let res = [];
// 迭代遍历 左中右
let cur = root;
let stack = [];
while (cur !== null || stack.length) {
if (cur !== null) {
stack.push(cur)
cur = cur.left
} else {
cur = stack.pop()
res.push(cur.val)
cur = cur.right
}
}
return res;
};
145. 二叉树的后序遍历
递归实现
var postorderTraversal = function(root) {
let res = [];
var traversal = function(root) {
if (root === null) {
return
}
traversal(root.left);
traversal(root.right);
res.push(root.val)
}
traversal(root)
return res;
};
迭代实现
- 与前序遍历相似，可以转换遍历顺序为根、右、左，再将其结果返回即可。
var postorderTraversal = function(root) {
if (!root) return []
let res = [];
let stack = [];
stack.push(root)
while(stack.length) {
let cur = stack.pop()
res.push(cur.val)
if (cur.left) {
stack.push(cur.left)
}
if (cur.right) {
stack.push(cur.right)
}
}
return res.reverse();
};
