前序遍历
根节点=>左子树=>右子树
遍历顺序为ABC
代码:
var preorderTraversal = function(root) {
let res = [];
// 遍历函数
function traversal(root) {
if (root !== null) {
// 访问根节点的值
res.push(root.val);
if (root.left) {
// 递归遍历左子树
traversal(root.left);
};
if (root.right) {
// 递归遍历右子树
traversal(root.right);
};
};
};
traversal(root);
return res;
};
中序遍历
中序遍历满足左子树=>根节点=>右子树的顺序进行查询
当跑到到根节点B时,先得看看有没有左子树,正好有,所以先遍历了左子树A之后才是B,最后遍历右子树C,所以完整顺序顺序为ABC。
题目来自 leetcode94. 二叉树的中序遍历 ,描述如下:
var inorderTraversal = function(root) {
let res = [];
// 遍历函数
function traversal(root) {
if (root !== null) {
if (root.left) {
// 递归遍历左子树
traversal(root.left);
};
// 访问根节点的值
res.push(root.val);
if (root.right) {
// 递归遍历右子树
traversal(root.right);
};
};
};
traversal(root);
return res;
};
后序遍历
后序遍历满足左子树=>右子树=>根节点的顺序进行查询,还是从简单二叉树开始:
从根节点C出发,先访问左子树A,紧接着右子树B,最后根节点C,所以顺序为ABC。
题目来自leetcode145. 二叉树的后序遍历 ,题目描述如下:
var postorderTraversal = function(root) {
let res = [];
// 遍历函数
function traversal(root) {
if (root !== null) {
if (root.left) {
// 递归遍历左子树
traversal(root.left);
};
if (root.right) {
// 递归遍历右子树
traversal(root.right);
};
// 访问根节点的值
res.push(root.val);
};
};
traversal(root);
return res;
};