剑指offer(22)从上往下打印二叉树

时间:2021-11-21 06:40:02

题目描述

从上往下打印出二叉树的每个节点,同层节点从左至右打印。

题目分析

从下打印就是按层次打印,其实也就是树的广度遍历。

一般来说树的广度遍历用队列,利用先进先出的特点来保存之前节点,并操作之前的节点。

树的深度遍历一般来说用栈或者递归,利用先进后出的特点来保存之前节点,把之前的节点留到后面操作。

代码

/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function PrintFromTopToBottom(root) {
const queue = [],
res = [];
if (root === null) {
return res;
}
queue.push(root);
while (queue.length) {
const pRoot = queue.shift();
if (pRoot.left !== null) {
queue.push(pRoot.left);
}
if (pRoot.right !== null) {
queue.push(pRoot.right);
}
res.push(pRoot.val);
}
return res;
}

此外,我们可以用递归来自己创建完全二叉树来做测试。

function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}
function createTree(n) {
if (n === 1) {
return new TreeNode(1);
}
const root = new TreeNode(n);
root.left = createTree(n - 1);
root.right = createTree(n - 1);
return root;
}
const tree = createTree(4);