从上往下打印二叉树
题目描述
从上往下打印出二叉树的每个节点,同层节点从左至右打印。
例如下图中的二叉树,则依次打印出8、 6、 10、 5、 7、 9、 11。
二叉树结点的定义如下:
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;}
}
思路:
这道题实质是在考查树的遍历算法。只是这种遍历不是我们熟悉的前序(根左右)、中序(左根右)、后序(左右根)遍历。
故就需要从树及打印列表分析。分析上图二叉树的层次打印顺序:
通过上图的具体例子的分析,我们可以找到从上到下打印二叉树的规律:每一次打印一个结点的时候,如果该结点有子结点,则把该结点的子结点放到队列的末尾。接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直至队列中所有的结点都被打印出来为止。
分层输出的方法:
也可以参考https://mp.****.net/postedit/83020604 ,写成
static public ArrayList<Integer> printFromTopToBottom(TreeNode node){}的形式
/**
* depth=3
* i=1,2,3 的时候,实现分别打印这一层
* 根节点 pTreeRoot
*/
static public void printFromTopToBottom(BinaryTreeNode pTreeRoot) {
if (pTreeRoot == null) {
return;
}
int depth = depth(pTreeRoot);
for (int i = 1; i <= depth; ++i) {
levelOrder(pTreeRoot, i);
}
}
如何打印这一层的具体实现:
static private void levelOrder(BinaryTreeNode pTreeNode, int level) {
if(pTreeNode == null || level < 1){//code1
return ;
}
if(level == 1){//code 2
System.out.print(pTreeNode.data+ " ");
return ;
}
/**
* 分析,当level>=2时候才执行,才会有level-1=1的情况出现
*/
//code3
//左子树
levelOrder(pTreeNode.left, level-1);
//右子树
levelOrder(pTreeNode.right, level-1);
}
step 1)在根节点,初始level=1,仅执行code1,输出8,其左右子节点无输出;
step2) level2,始level=2;仅执行code3,于是
levelOrder(8.left, level-1)= levelOrder(6, 1)=6
levelOrder(8.right, level-1)=levelOrder(10, 1)=10
仅输出根节点的左右节点;
step3)level=3, ...
二叉树深度计算的递归实现:
/**
* 计算二叉树深度,例如depth(8)=3;depth(6)=2;
* depth(5)=1
* @param pTreeRoot
* @return
*/
static private int depth(BinaryTreeNode pTreeRoot){
if(pTreeRoot==null){
return 0;
}
int l = depth(pTreeRoot.left);
int r = depth(pTreeRoot.right);
if(l > r){
return l + 1;
}else{
return r + 1;
}
}
分析,
难点1)二叉树深度计算的递归实现
图形表示:
测试用例 :
import java.util.ArrayList;
public class printArrayList {
//层序遍历二叉树递归实现
/**
* 计算节点高度,例如depth(8)=3;depth(6)=2;
* depth(5)=1
* @param pTreeRoot
* @return
*/
static private int depth(TreeNode pTreeRoot){
if(pTreeRoot==null){
return 0;
}
int l = depth(pTreeRoot.left);
int r = depth(pTreeRoot.right);
if(l > r){
return l + 1;
}else{
return r + 1;
}
}
static private void levelOrder(TreeNode pTreeNode, int level) {
if(pTreeNode == null || level < 1){
return ;
}
if(level == 1){
System.out.print(pTreeNode.val+ " ");
return ;
}
/**
* 分析,当level>=2时候才执行,才会有level-1=1的情况出现
*/
//左子树
levelOrder(pTreeNode.left, level-1);
//右子树
levelOrder(pTreeNode.right, level-1);
}
/**
* depth=3
* i=1,2,3 的时候,实现分别打印这一层
* 根节点 pTreeRoot
*/
static public ArrayList<Integer> PrintFromTopToBottom(TreeNode node) {
ArrayList<Integer> list=new ArrayList<>();
//printFromTopToBottom(node);
if (node == null) {
return list;
}
int depth = depth(node);
for (int i = 1; i <= depth; ++i) {
levelOrder(node, i);
}return list;
}
public static void main(String[] args) {
TreeNode root=new TreeNode(8);
root.left = new TreeNode(6);
root.right = new TreeNode(10);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(11);
PrintFromTopToBottom(root.left);
}
}
参考:https://blog.****.net/u013132035/article/details/80604718
依然有很多学习与整理的的地方,可参考上面的链接,属于一个比较完整的归纳。例如
1)非递归方式实现;
2)二叉树深度计算的非递归实现;
3)二叉树的前序、中序列、后序遍历的实现与输出结果。
注明:前序遍历的输出结果为:[8, 6, 5, 7, 10, 9, 11]
前序遍历的代码:
//前序遍历二叉树
static ArrayList<Integer> list = new ArrayList<Integer>();
static public ArrayList<Integer> preOrderBinaryTree(BinaryTreeNode pTreeRoot) {
if (pTreeRoot != null) {
list.add(pTreeRoot.data); //先根结点
preOrderBinaryTree(pTreeRoot.left); //再左边节点调用前序遍历
preOrderBinaryTree(pTreeRoot.right); //再右边节点调用前序遍历
} else {
return null;
}
return list;