우선 순위 에 따라 이 진 트 리 를 구축 합 니 다.
17517 단어 매일 알고리즘
: :1,2,4,7,3,5,6,8
:4,7,2,1,5,3,6,8
:7,4,2,5,8,6,3,1
1:
:
1. ;
2.
3. 1 2
4.
5.
package com.banban.CeShi.BinaryTree;
/**
* @author :zhangpengzhan
* @date :Created in 2019/4/2 19:54
* @name :BinaryTreeNode
*/
public class BinaryTreeNode {
private int value;
private BinaryTreeNode leftNode;
private BinaryTreeNode rightNode;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public BinaryTreeNode getLeftNode() {
return leftNode;
}
public void setLeftNode(BinaryTreeNode leftNode) {
this.leftNode = leftNode;
}
public BinaryTreeNode getRightNode() {
return rightNode;
}
public void setRightNode(BinaryTreeNode rightNode) {
this.rightNode = rightNode;
}
@Override
public String toString() {
return "BinaryTreeNode{" +
"value=" + value +
'}';
}
}
:
package com.banban.CeShi.BinaryTree;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author :zhangpengzhan
* @date :Created in 2019/4/2 19:41
* @name :ReBuildTree
*
* ,
*
* : :1,2,4,7,3,5,6,8
* :4,7,2,1,5,3,6,8
*
* :7,4,2,5,8,6,3,1
*
* 1:
* :
* 1. ;
* 2.
* 3. 1 2
* 4.
* 5.
*
*/
public class ReBuildTree {
//private static ArrayList arrayList = new ArrayList<>();
public static BinaryTreeNode buildTree(int[] pre,int[] ord){
if (pre.length == 0 ||ord.length == 0){
return null;
}
BinaryTreeNode treeNode = new BinaryTreeNode();
treeNode.setValue(pre[0]);
for (int i = 0; i <ord.length ; i++) {
if (ord[i]==pre[0]){
treeNode.setLeftNode(buildTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(ord,0,i)));
treeNode.setRightNode(buildTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(ord,i+1,ord.length)));
}
}
return treeNode;
}
public static void postTree(BinaryTreeNode treeNode){
if (treeNode != null){
postTree(treeNode.getLeftNode());
postTree(treeNode.getRightNode());
//arrayList.add(treeNode.getValue());
System.out.println(treeNode.getValue());
}
}
// public static void postCover(int[] pre, int[] ord,int[] post,int index){
// for (int i = 0; i
// if (pre[0] == ord[i]){
// post[index] = ord[i];
// //
// postCover(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(ord,0,i),post,i-1);
// //
// postCover(Arrays.copyOfRange(pre,i+1,pre.length), Arrays.copyOfRange(ord,i+1,ord.length),post,index-1);
//
// }
// }
// }
public static void main(String[] args) {
int[] pre = new int[]{1,2,4,7,3,5,6,8};
int[] ord = new int[]{4,7,2,1,5,3,8,6};
int[] post = new int[8];
BinaryTreeNode tree = buildTree(pre, ord);
postTree(tree);
}
}