#データ構造とアルゴリズム学習ノート#剣指Offer 58:ツリーを複数行に印刷(Java、C/C++)
3356 ワード
2019.2.27 《剣指Offer》零单刷个人笔记整理(66题全)目次転送扉
実はこの問題は層順に二叉木を遍歴することで、前にすでに書いた:#データ構造とアルゴリズム学習ノート#剣指Offer 21:上から二叉木を印刷する/階層遍歴二叉木(Java、C/C++)
復習に相当して、何も言うことはありません.難点は前の問題で、二叉木を字型で印刷する:#データ構造とアルゴリズム学習ノート#剣指Offer 57:二叉木を字型順に印刷する(Java、C/C++)
タイトルの説明
ツリーを上から下へレイヤ別に印刷し、同じレイヤのノードを左から右に出力します.各層に1行出力します.
Java実装:
C++実装例:
#Coding 1時間、Copying 1秒.いいねを残してくれてありがとう
実はこの問題は層順に二叉木を遍歴することで、前にすでに書いた:#データ構造とアルゴリズム学習ノート#剣指Offer 21:上から二叉木を印刷する/階層遍歴二叉木(Java、C/C++)
復習に相当して、何も言うことはありません.難点は前の問題で、二叉木を字型で印刷する:#データ構造とアルゴリズム学習ノート#剣指Offer 57:二叉木を字型順に印刷する(Java、C/C++)
タイトルの説明
ツリーを上から下へレイヤ別に印刷し、同じレイヤのノードを左から右に出力します.各層に1行出力します.
Java実装:
/**
*
* @author ChopinXBP
* , 。 。
*
*/
import java.util.ArrayList;
import java.util.LinkedList;
public class PrintTree_59 {
public static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode pHead = new TreeNode(0);
TreeNode p1= new TreeNode(1);
TreeNode p2= new TreeNode(2);
TreeNode p3= new TreeNode(3);
TreeNode p4= new TreeNode(4);
TreeNode p5= new TreeNode(5);
TreeNode p6= new TreeNode(6);
pHead.left = p1;
pHead.right = p2;
p1.left = p3;
p1.right = p4;
p2.left = p5;
p2.right = p6;
ArrayList> result = Print(pHead);
for(int i = 0; i < result.size(); i++) {
for(int j = 0; j < result.get(i).size(); j++) {
System.out.print(result.get(i).get(j) + " ");
}
System.out.println(" ");
}
}
public static ArrayList> Print(TreeNode pRoot) {
ArrayList> result = new ArrayList<>();
if(pRoot == null)return result;
LinkedList tree = new LinkedList<>();
tree.add(pRoot);
while(!tree.isEmpty()) {
TreeNode pNode;
ArrayList list = new ArrayList<>();
int num = tree.size();
for (int i = 0; i < num; i++) {
pNode = tree.pollFirst();
if (pNode.left != null) {
tree.add(pNode.left);
}
if (pNode.right != null) {
tree.add(pNode.right);
}
list.add(pNode.val);
}
if(!list.isEmpty()) result.add(list);
}
return result;
}
}
C++実装例:
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector > Print(TreeNode* pRoot) {
vector > vv;
vector ve;
queue que;
queue dque;
int depth=0;
que.push(pRoot);
dque.push(depth);
TreeNode *node;
while(!que.empty()){
node=que.front();
if(depth!=dque.front()){
vv.push_back(ve);
ve.clear();
depth=dque.front();
}
que.pop();
dque.pop();
if(node){
que.push(node->left);
que.push(node->right);
dque.push(depth+1);
dque.push(depth+1);
ve.push_back(node->val);
}
}
return vv;
}
};
#Coding 1時間、Copying 1秒.いいねを残してくれてありがとう