Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

【leetcode】【JavaScript】二叉树

咕啾啾 2022-08-06 10:14:30 阅读数:2 评论数:0 点赞数:0 收藏数:0

一、二叉树理论知识

二、二叉树的深度优先遍历(前序 + 中序 + 后序)

1、递归法

1.1 前序遍历

//【递归】前序遍历:中左右
var preorderTraversal = function(root) {
let res = [];
const dfs = (root) => {
if(root === null) return ;
// 先序遍历所以从父节点开始
res.push(root.val);
// 递归左子树
dfs(root.left);
// 递归右子树
dfs(root.right);
}
dfs(root);
};

1.2 中序遍历

// 【递归】中序遍历:左中右
var inorderTraversal = function(root) {
let res = [];
const dfs = (root) => {
if(root === null) return ;
// 遍历左子树
dfs(root.left);
res.push(root.val);
dfs(root.right);
}
dfs(root);
return res;
};

1.3 后序遍历

// 【递归】后序遍历:左右中
var postorderTraversal = function(root) {
let res = [];
const dfs = (root) => {
if(root === null) return ;
dfs(root.left);
dfs(root.right);
res.push(root.val);
}
dfs(root);
return res;
};

2、二叉树的迭代遍历

2.1 前序遍历

// 入栈 右 -> 左
// 出栈 中 -> 左 -> 右
var preorderTraversal = function(root, res = []) {
if(!root) return res;
const stack = [root];
let cur = null;
while(stack.length) {
cur = stack.pop();
res.push(cur.val);
if(cur.right) stack.push(cur.right);
if(cur.left) stack.push(cur.left);
}
return res;
};

2.2 中序遍历

// 入栈 左 -> 右
// 出栈 左 -> 中 -> 右
var inorderTraversal = function(root, res = []) {
const stack = [];
let cur = root;
while(stack.length || cur) {
if(cur) {
stack.push(cur);
// 左
cur = cur.left;
} else {
// --> 弹出 中
cur = stack.pop();
res.push(cur.val);
// 右
cur = cur.right;
}
};
return res;
};

2.3 后序遍历

// 入栈 左 -> 右
// 出栈 中 -> 右 -> 左 结果翻转
var postorderTraversal = function(root, res = []) {
if (!root) return res;
const stack = [root];
let cur = null;
do {
cur = stack.pop();
res.push(cur.val);
if(cur.left) stack.push(cur.left);
if(cur.right) stack.push(cur.right);
} while(stack.length);
return res.reverse();
};

三、二叉树的广度优先遍历(层序遍历)

1、理解

        代码随想录

2、code 

var levelOrder = function(root) {
let res = [];
// 如果二叉树为空,直接返回空数组
if(!root) return res;
// 定义一个队列操作存储节点
let queue = [root];
while(queue.length){
// list 存放每一层的节点值
let list = [];
// 记录当前队列(也就是队列某层)的长度并遍历这一层所有的节点
let length = queue.length;
while(length--){
// 将当前节点出队列,并将节点值加到 list
let node = queue.shift();
list.push(node.val);
// 判断当前节点有没有左右节点,有就加入队列
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
// 如果是自底向上的话:res.unshift(curLevel);
res.push(list);
}
return res;
};

版权声明
本文为[咕啾啾]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_30148319/article/details/126149324

支付宝红包,每日可领(支付宝免费1-2元支付红包)