js
// 3
// / \
// 1 4
// \
// 2
- 中序遍历（左根右）：
1 2 3 4 - 前序遍历（根左右）：
3 1 2 4 - 后序遍历（左右根）：
2 1 4 3
- dfs 通过栈实现（x 序遍历）
- bfs 通过队列实现（层序遍历）
二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
递归版本
js
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function (root) {
if (!root) return [];
return [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)];
};
栈版本
js
var preorderTraversal = function (root) {
if (!root) return [];
let stack = [root];
let result = [];
while (stack.length) {
const node = stack.pop();
result.push(node.val);
node.right && stack.push(node.right); // 注意 先进后出 这里是右节点先进，然后后出
node.left && stack.push(node.left);
}
return result;
};
二叉树的后序遍历
js
var postorderTraversal = function (root) {
if (!root) return [];
return [...postorderTraversal(root.left), ...postorderTraversal(root.right), root.val];
};
二叉树的中序遍历
js
var inorderTraversal = function (root) {
if (!root) return [];
return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)];
};
二叉树的层序遍历
- leetcode：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
js
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
js
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function (root) {
if (!root) return [];
let result = [];
let queue = [root];
while (queue.length) {
let len = queue.length;
let temp = [];
for (let i = 0; i < len; i++) {
let node = queue.shift();
temp.push(node.val);
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
result.push(temp);
}
return result;
};