不分行从上往下打印出二叉树的每个节点,同层节点从左至右打印。例如输入{8,6,10,#,#,2,1},如以下图中的示例二叉树,则依次打印8,6,10,2,1(空节点不打印,跳过),请你将打印的结果存放到一个数组里面,返回。
数据范围:
0<=节点总数<=1000
-1000<=节点值<=1000
{8,6,10,#,#,2,1}
[8,6,10,2,1]
{5,4,#,3,#,2,#,1}
[5,4,3,2,1]
import java.util.*; public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> res = new ArrayList<>(); if(root == null) return res; List<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ TreeNode node = queue.remove(0); res.add(node.val); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } return res; } }
python solution easy to understand:
def PrintFromTopToBottom(self, root): if not root: return [] currentStack = [root] res = [] while currentStack: nextStack = [] for i in currentStack: if i.left: nextStack.append(i.left) if i.right: nextStack.append(i.right) res.append(i.val) currentStack = nextStack return res
/** 思路是用arraylist模拟一个队列来存储相应的TreeNode */ public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> list = new ArrayList<>(); ArrayList<TreeNode> queue = new ArrayList<>(); if (root == null) { return list; } queue.add(root); while (queue.size() != 0) { TreeNode temp = queue.remove(0); if (temp.left != null){ queue.add(temp.left); } if (temp.right != null) { queue.add(temp.right); } list.add(temp.val); } return list; } }
class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { vector<int> res; if(root==NULL) return res; queue<TreeNode*> q; q.push(root); while(!q.empty()){ res.push_back(q.front()->val); if(q.front()->left!=NULL) q.push(q.front()->left); if(q.front()->right!=NULL) q.push(q.front()->right); q.pop(); } return res; } };
class Solution { public: vector<int> PrintFromTopToBottom(TreeNode *rt) { queue<TreeNode*> q; q.push(rt); vector<int> r; while(!q.empty()){ rt = q.front(); q.pop(); if(!rt) continue; r.push_back(rt -> val); q.push(rt -> left); q.push(rt -> right); } return r; } };
public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); if(root==null){ return list; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode treeNode = queue.poll(); if (treeNode.left != null) { queue.offer(treeNode.left); } if (treeNode.right != null) { queue.offer(treeNode.right); } list.add(treeNode.val); } return list; } }
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回从上到下每个节点值列表,例:[1,2,3] def PrintFromTopToBottom(self, root): # write code here if not root: return [] queue = [] result = [] queue.append(root) while len(queue) > 0: node = queue.pop(0) result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result
public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<TreeNode> listNode=new ArrayList<TreeNode> (); ArrayList<Integer> listVal=new ArrayList<Integer> (); if(root==null) return listVal; listNode.add(root); listVal.add(root.val); for(int i=0;i<listNode.size();i++){ TreeNode node= listNode.get(i); if(node.left!=null){ listNode.add(node.left); listVal.add(node.left.val); } if(node.right!=null){ listNode.add(node.right); listVal.add(node.right.val); } } return listVal; } }
class Solution { public: vector<int> PrintFromTopToBottom(TreeNode *root) { vector<int> res; vector<TreeNode *> array; if(root == NULL) return res; array.push_back(root); int p = 0; while(p < array.size()){ TreeNode * temp = array[p++]; if(temp->left) array.push_back(temp->left); if(temp->right) array.push_back(temp->right); res.push_back(temp->val); } return res; } };
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { vector<int> result; if(NULL == root) return result; queue<TreeNode* > q; q.push(root); while(!q.empty()) { TreeNode* temp = q.front(); q.pop(); result.push_back(temp->val); if(NULL != temp->left) q.push(temp->left); if(NULL != temp->right) q.push(temp->right); } return result; } };
这是一道树的广度优先遍历的题,建议对这方面知识不明白的朋友先去了解一下广度优先遍历和深度优先遍历的原理。
推荐篇文章,使用js实现的:https://segmentfault.com/a/1190000008954436
//树的广度优先遍历
function PrintFromTopToBottom(root)
{
var nodes = [];
var leafs = [];
if(!root){
return false;
}
nodes.push(root);
while(nodes && nodes.length>0){
var node = nodes.shift();
leafs.push(node.val)
if(node.left){
nodes.push(node.left)
}
if(node.right){
nodes.push(node.right)
}
}
return leafs;
}
经典的宽度优先搜索 队列实现
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> v;
if(root == NULL) return v;
queue<TreeNode*> q; q.push(root);
while(!q.empty()){
TreeNode* tmp = q.front(); q.pop();
v.push_back(tmp->val);
if(tmp->left != NULL) q.push(tmp->left);
if(tmp->right != NULL) q.push(tmp->right);
}
return v;
}
};
class Solution: def PrintFromTopToBottom(self, root): if not root: return [] # write code here ls=[root] result=[] while len(ls)>0: node=ls.pop(0) result.append(node.val) if node.left!=None: ls.append(node.left) if node.right!=None: ls.append(node.right) return result
import java.util.ArrayList; import java.util.LinkedList; public class Solution { //层序遍历,用队列,非递归 public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> resList = new ArrayList<>(); if(root == null) return resList; //queue用LinkedList实现 LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ //queue里面没有null TreeNode tempNode = queue.poll(); resList.add(tempNode.val); if(tempNode.left != null) queue.add(tempNode.left); if(tempNode.right != null) queue.add(tempNode.right); } return resList; } }
class Solution: # 返回从上到下每个节点值列表,例:[1,2,3] def PrintFromTopToBottom(self, root): # write code here res,queue = [],[] if root == None: return res queue.append(root) while queue: node = queue.pop(0) res.append(node.val) if node.left != None: queue.append(node.left) if node.right !=None: queue.append(node.right) return res
class Solution: def PrintFromTopToBottom(self, root): layer_list = [root] if root is None: return [] for node in layer_list: # 遍历每一层,元素加到列表末尾 if node.left: layer_list.append(node.left) if node.right: layer_list.append(node.right) return [i.val for i in layer_list]有比我这更简单的吗?哈哈哈,使了点小聪明,动态改变循环的列表,也达到了队列的效果
此题是要求将二叉树进行层序遍历,使用队列模拟层序遍历元素的打印顺序,将元素加入到ArrayList。 import java.util.ArrayList; import java.util.LinkedList;import java.util.Queue;public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { if (root == null) { return new ArrayList<Integer>(); } Queue<TreeNode> arrlist = new LinkedList<TreeNode>(); ArrayList<Integer> res = new ArrayList<Integer>(); arrlist.add(root); while (!arrlist.isEmpty()) { TreeNode cur = arrlist.poll(); //System.out.println(cur.val); res.add(cur.val); if (cur.left != null) { arrlist.add(cur.left); } if (cur.right != null) { arrlist.add(cur.right); } } return res; } }
public class Solution { //层序遍历 ArrayList<Integer> list=new ArrayList<Integer>(); boolean flag=true; int i=0; int count=0; public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<TreeNode> tn=new ArrayList<TreeNode>();//用于保存当前节点的左右子节点 if(root !=null){ tn.add(root); while(flag){ if(root.left !=null){ //添加左子树 tn.add(root.left ); count++; } if(root.right !=null){ //添加右子树 tn.add(root.right); count++; } if(i<count){ i++; root=tn.get(i);//准备添加下一个节点的左右子节点 }else{ flag=false; } } } for(int j=0;j<tn.size();j++){ list.add(tn.get(j).val); } return list; } }
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> res;
if(root == NULL)
return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
TreeNode *tmp = q.front();
res.push_back(tmp->val);
if(tmp->left != NULL) {
q.push(tmp->left);
}
if(tmp->right != NULL) {
q.push(tmp->right);
}
q.pop();
}
return res;
}
};
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { vector<int> res; if(root==NULL) //需要判断是否为空 return res; deque<TreeNode*> dequeTreeNode; dequeTreeNode.push_back(root); while(dequeTreeNode.size()) //循环终止条件:队列元素全部打印为空 { TreeNode* pNode= dequeTreeNode.front(); //返回双端队列dequeTreeNode的首元素给pNode dequeTreeNode.pop_front(); //删除双端队列dequeTreeNode的首元素 res.push_back(pNode->val); //将此时的dequeTreeNode第一个元素存入到输出容器res中 if(pNode->left) //若当前结点的左结点不为空,将其左结点存入到双端队列dequeTreeNode中 dequeTreeNode.push_back(pNode->left); if(pNode->right) dequeTreeNode.push_back(pNode->right); ////若当前结点的右结点不为空,将其右结点存入到双端队列dequeTreeNode中 } return res; } };
function PrintFromTopToBottom(root) { // write code here var arr = [], arrVal = []; if(!root){ return arrVal; } arr.push(root); while(arr.length){ var cur = arr.shift(); arrVal.push(cur.val); if(cur.left){ arr.push(cur.left); } if(cur.right){ arr.push(cur.right); } } return arrVal; }