题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
}
}
分析思路
错误思路
错误代码
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(root == null) return null;
while(root != null){//这里判断终止条件，将会是一个死循环
list.add(root.val);
if(root.left != null) PrintFromTopToBottom(root.left);
if(root.right != null) PrintFromTopToBottom(root.right);
}
return list;
}
错误分析
之所以一开始就想到了用递归的方式来做，还是由于对递归的本质没有了解清楚。同时也是对本题的深层含义没有了解清楚（本题实际上是在求二叉树的广度优先遍历，而不是深度优先遍历）。如果按照递归的思想来做的话实际上是一种前序遍历
正确思路
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(root == null) return list;//注意处理空指针的情况 考虑要周全，这里root==null时返回null会报空指针，所以应该返回list
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()){
TreeNode curNode = queue.pollFirst();
list.add(curNode.val);
if(curNode.left != null){
queue.addLast(curNode.left);
}
if(curNode.right != null){
queue.addLast(curNode.right);
}
}
return list;
}