文章目录
1. 剑指 Offer 32 - I. 从上到下打印二叉树
二叉树的广度优先遍历
/*
1. 队列存入树结构
2. 队列先入先出特性来遍历二叉树
*/
var levelOrder = function(root) {
if(!root) return [];
// 根节点存入队列
const q = [root];
const res = [];
while(q.length){
// 出队
let node = q.shift();
// 值存入res数组
res.push(node.val);
// 不为空则入队
node.left && q.push(node.left);
node.right && q.push(node.right);
}
return res;
}
2. 剑指 Offer 32 - II. 从上到下打印二叉树 II
原题链接
二叉树的层序遍历、双重循环
/*
1. 定义一个tmp数组来存储每一层的数据
2. 将tmp添加到res中
*/
var levelOrder = function(root) {
if(!root) return [];
const q = [root];
const res = [];
while(q.length){
const tmp = [];
for(let i = q.length; i>0; i--){
let node = q.shift();
tmp.push(node.val);
node.left && q.push(node.left);
node.right && q.push(node.right);
}
res.push(tmp);
}
return res;
}
3. 剑指 Offer 32 - III. 从上到下打印二叉树 III
原题链接
要求打印顺序交替变化
/*
1. 定义flag来判断层数
2. 层数为奇数将数值添加到数组末尾 tmp.push()
层数为偶数将数值添加到数组开头 tmp.unshift()
*/
var levelOrder = function(root) {
if(!root) return [];
const q = [root];
const res = [];
let flag = 0;
while(q.length){
const tmp = [];
for(let i=q.length; i>0; i--){
let node = q.shift();
if(flag%2===0)tmp.push(node.val);
else tmp.unshift(node.val);
node.left && q.push(node.left);
node.right && q.push(node.right);
}
flag++;
res.push(tmp);
}
return res;
}
4. 剑指 Offer 34. 二叉树中和为某一值的路径
回溯（做选择，做完选择后回复做选择前的状态）
/*
1. 先序遍历，遍历树所有节点
2. 路径记录，遍历过程中，记录从根节点到当前节点的路径，当路径满足条件则加入结果集。
条件：到达叶子节点 且 路径中各节点值之和等于目标值。
*/
var pathSum = function(root, target) {
let res = [];
const backtrack = (root, path, sum)=>{
if(!root) return null;
// 路径加入当前节点值
path.push(root.val);
sum += root.val;
// 条件判断
if(root.left == null && root.right == null && sum == target){
// slice方法会返回一个新数组
res.push(path.slice());
}
// 遍历
backtrack(root.left, path, sum);
backtrack(root.right, path, sum);
// 回溯
sum -= root.val;
path.pop();
}
backtrack(root, [], 0);
return res;
}
5. 剑指 Offer 36. 二叉搜索树与双向链表
二叉搜索树的性质：左节点 < 当前节点 < 右节点
/*
1. 中序遍历可以从小到大访问节点
2. 对于题中要构造的双向链表需要 pre.right = cur cur.left = pre
3. 循环即对于头节点和尾节点需要 head.left = tail tail.right = head
*/
var treeToDoublyList = function(root) {
if(!root) return null;
let head = null;
let pre = null; // 先驱节点
// 中序遍历
const inorder = (node)=>{
if(!node) return;
inorder(node.left);
if(pre){
// 先驱节点与当前节点
pre.right = node;
node.left = pre;
}else{
// 此时递归到了最左边的节点
// 最左边的节点就是最小的，是头节点
head = node;
}
pre = node;
inorder(node.right);
}
inorder(root);
// 头节点和尾节点
pre.right = head;
head.left = pre;
return head;
}
