ツリーの一般的なアルゴリズム操作
19837 ワード
ツリーはデータ構造の重要な一部であり、各大手企業の面接常考部分でもある.
ツリーの様々な遍歴アルゴリズムに続いて、今日はツリーの一般的なアルゴリズム操作を整理します.
この文書には、次のものが含まれます.
1.ノードの最近の共通祖先を求める
2.ツリーのシーケンス化と逆シーケンス化
3.先順遍歴と中順遍歴が知られている二叉木
4.既知の中序遍歴と後序遍歴による二叉木の構築
1.ノードの最も近い共通の祖先を求める
この問題の異なる要求には異なる解法がある.
既知のツリー内の各ノードに親ノードへのポインタがある場合:
構想:指定したノードからルートノードに遍歴し、親ノードが等しい場合に返します.
解法1
解法2:
ツリー内のノードに親ノードへのポインタがない場合:
構想は先序遍歴と中序遍歴の特徴を利用して、先序遍歴を利用してルートノードを分解し、ルートノードと所与のノードABの位置関係に基づいて共通の祖先を確定し、中序遍歴の結果に基づいて、2つのノードの中間のノードは求めた祖先であり、中間にノードがなければ、中序遍歴の中で下のスケールが小さいのは祖先である.
2.ツリーのシーケンス化と逆シーケンス化
ツリーのノードをファイルに格納し、ツリーを構築するシーケンス化と逆シーケンス化をファイルから読み出します.
構想:先順遍歴(他の遍歴でもよい)を利用して、木のノード値を文字列に格納し、ノードが空であれば#を格納し、各ノード間を','で区切って数字を区別する.
読み出し時にも先順で遍歴する方法があります.
3.先順遍歴と中順遍歴が知られている二叉木
構想:先順遍歴でルートノードを区別し,中順遍歴で左右のサブツリーを区別する
4.既知の中序遍歴と後序遍歴による二叉木の構築
構想:前者と構想の差は多くなく,後序遍を利用して従来からルートノードを探し,中序遍歴を利用して左右のサブツリーを分解する
ツリーの様々な遍歴アルゴリズムに続いて、今日はツリーの一般的なアルゴリズム操作を整理します.
この文書には、次のものが含まれます.
1.ノードの最近の共通祖先を求める
2.ツリーのシーケンス化と逆シーケンス化
3.先順遍歴と中順遍歴が知られている二叉木
4.既知の中序遍歴と後序遍歴による二叉木の構築
1.ノードの最も近い共通の祖先を求める
この問題の異なる要求には異なる解法がある.
既知のツリー内の各ノードに親ノードへのポインタがある場合:
構想:指定したノードからルートノードに遍歴し、親ノードが等しい場合に返します.
解法1
private ArrayList<TreeNode> getPath2Root(TreeNode node) {
ArrayList<TreeNode> list = new ArrayList<TreeNode>();
while (node != null) {
list.add(node);
node = node.parent;
}
return list;
}
public TreeNode lowestCommonAncestor(TreeNode node1, TreeNode node2) {
ArrayList<TreeNode> list1 = getPath2Root(node1);
ArrayList<TreeNode> list2 = getPath2Root(node2);
int i, j;
for (i = list1.size() - 1, j = list2.size() - 1; i >= 0 && j >= 0; i--, j--) {
if (list1.get(i) != list2.get(j)) {
return list1.get(i).parent;
}
}
return list1.get(i+1);
}
解法2:
private TreeNode getRoot(node) {
while (node.parent != null) {
node = node.parent;
}
return node;
}
private TreeNode getAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
if (root == null || root == node1 || root == node2) {
return root;
}
TreeNode left = getAncestor(root.left, node1, node2);
TreeNode right = getAncestor(root.right, node1, node2);
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
if (right != null) {
return right;
}
return null;
}
public TreeNode lowestCommonAncestor(TreeNode node1, TreeNode node2) {
if (node1 == null || node2 == null) {
return null;
}
TreeNode root = getRoot(node1);
return getAncestor(root, node1, node2);
}
ツリー内のノードに親ノードへのポインタがない場合:
構想は先序遍歴と中序遍歴の特徴を利用して、先序遍歴を利用してルートノードを分解し、ルートノードと所与のノードABの位置関係に基づいて共通の祖先を確定し、中序遍歴の結果に基づいて、2つのノードの中間のノードは求めた祖先であり、中間にノードがなければ、中序遍歴の中で下のスケールが小さいのは祖先である.
TreeNode node =null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
// write your code here
TreeNode result =null;
ArrayList<TreeNode> inorder = new ArrayList<TreeNode>();
ArrayList<TreeNode> preorder = new ArrayList<TreeNode>();
inorderto(root,inorder);
preorderto(root,preorder);
// AB
int aValue = inorder.indexOf(A);
int bValue = inorder.indexOf(B);
int lastindex = 0 ;
for(int i=0;i<preorder.size();){
int rootValue = inorder.indexOf(preorder.get(i));
if((aValue<=rootValue && bValue>=rootValue)||(aValue>=rootValue && bValue<=rootValue)){
result = preorder.get(i);
break;
}
else
i++;
}
return result;
}
public void inorderto(TreeNode root,ArrayList<TreeNode> list){
if(root==null)
return;
else{
inorderto(root.left,list);
list.add(root);
inorderto(root.right,list);
}
}
public void preorderto(TreeNode root,ArrayList<TreeNode> list){
if(root==null)
return;
else{
list.add(root);
preorderto(root.left,list);
preorderto(root.right,list);
}
}
2.ツリーのシーケンス化と逆シーケンス化
ツリーのノードをファイルに格納し、ツリーを構築するシーケンス化と逆シーケンス化をファイルから読み出します.
構想:先順遍歴(他の遍歴でもよい)を利用して、木のノード値を文字列に格納し、ノードが空であれば#を格納し、各ノード間を','で区切って数字を区別する.
読み出し時にも先順で遍歴する方法があります.
public String serialize(TreeNode root) {
// write your code here
String str = "";
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root!=null)
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
if(node!=null){
str += node.val + ",";
stack.push(node.right);
stack.push(node.left);
}
else
str += "#,";
}
return str;
}
int index =0 ;
public TreeNode deserialize(String data) {
if(data=="")
return null;
String val = outValue(index,data);
index += 1;
if(val.equals("#"))
return null;
else{
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = deserialize(data);
node.right = deserialize(data);
return node;
}
}
public String outValue(int index,String str){
String res = "";
for(int i=0,j=0;i<str.length();i++){
if(str.charAt(i)==',')
j++;
else if(j==index)
res += str.charAt(i);
if(j>index)
break;
}
return res;
}
3.先順遍歴と中順遍歴が知られている二叉木
構想:先順遍歴でルートノードを区別し,中順遍歴で左右のサブツリーを区別する
private int findPosition(int[] arr, int start, int end, int key) {
int i;
for (i = start; i <= end; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}
private TreeNode myBuildTree(int[] inorder, int instart, int inend,
int[] preorder, int prestart, int preend) {
if (instart > inend) {
return null;
}
TreeNode root = new TreeNode(preorder[prestart]);
int position = findPosition(inorder, instart, inend, preorder[prestart]);
root.left = myBuildTree(inorder, instart, position - 1,
preorder, prestart + 1, prestart + position - instart);
root.right = myBuildTree(inorder, position + 1, inend,
preorder, position - inend + preend + 1, preend);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (inorder.length != preorder.length) {
return null;
}
return myBuildTree(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1);
}
4.既知の中序遍歴と後序遍歴による二叉木の構築
構想:前者と構想の差は多くなく,後序遍を利用して従来からルートノードを探し,中序遍歴を利用して左右のサブツリーを分解する
public TreeNode buildTree(int[] inorder, int[] postorder) {
// write your code here
if(inorder.length != postorder.length)
return null;
return myTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
}
public TreeNode myTree(int[]inorder,int instart,int inend,
int[] postorder,int poststart,int postend){
if(instart>inend)
return null;
TreeNode root = new TreeNode(postorder[postend]);
int position = findPosition(inorder,instart,inend,postorder[postend]);
root.left = myTree(inorder,instart,position-1,postorder,poststart,poststart+position-1-instart);
root.right = myTree(inorder,position+1,inend,postorder,position - inend + postend ,postend-1);
return root;
}
private int findPosition(int[] arr, int start, int end, int key) {
int i;
for (i = start; i <= end; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}