157 将搜索二叉树转换成双向链表
ac
- Java的输入输出耗时太久了，使用
StringBuilder
- 递归建立树和非递归建立树均可以
- 非递归中序遍历
最初思路AC
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class DoubleListNode{
int val;
DoubleListNode pre;
DoubleListNode next;
public DoubleListNode(int val) {
this.val = val;
pre = null;
next = null;
}
}
class DoubleList{
DoubleListNode head;
DoubleListNode tail;
public DoubleList() {
head = null;
tail = null;
}
void addTail(int val){
if(head == null){
head = new DoubleListNode(val);
tail = head;
}else {
DoubleListNode node = new DoubleListNode(val);
tail.next = node;
node.pre = tail;
tail = node;
}
}
void printList(){
if(head == null){
return;
}
boolean flag = true;
DoubleListNode p = head;
StringBuilder sb = new StringBuilder();
while (p != null){
if(flag){
sb.append(p.val);
flag = false;
}else {
sb.append(" " + p.val);
}
p = p.next;
}
System.out.println(sb.toString());
}
}
class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
left = null;
right = null;
}
}
public class Main {
public static Scanner sc = new Scanner(System.in);
public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
public static long mod = (long)Math.pow(2,29);
static Map<Integer, Integer> leftArr = new HashMap<>();
static Map<Integer, Integer> rightArr = new HashMap<>();
// 递归建立树
static TreeNode buildTree(TreeNode root, int val){
if(root == null){
root = new TreeNode(val);
}
int left = leftArr.get(val);
int right = rightArr.get(val);
if(left != 0){
root.left = buildTree(root.left, left);
}
if(right != 0){
root.right = buildTree(root.right, right);
}
return root;
}
public static void main(String[] args) throws Exception{
int n = Integer.valueOf(reader.readLine());
int rootVal = -1;
for (int i = 0; i < n; i++) {
String line = reader.readLine();
String[] strArr = line.split(" ");
int curVal = Integer.valueOf(strArr[0]);
int leftVal = Integer.valueOf(strArr[1]);
int rightVal = Integer.valueOf(strArr[2]);
leftArr.put(curVal,leftVal);
rightArr.put(curVal, rightVal);
if(rootVal == -1){
rootVal = curVal;
}
}
TreeNode root = null;
root = buildTree(root, rootVal);
DoubleList doubleList = searchTree2DoubleLink(root);
doubleList.printList();
}
// 搜索二叉树转双向链表
static DoubleList searchTree2DoubleLink(TreeNode root){
if(root == null){
return null;
}
DoubleList doubleList = new DoubleList();
// 非递归中序遍历
TreeNode cur = root;
while (cur != null){
if (cur.left == null){
// 打印
doubleList.addTail(cur.val);
cur = cur.right;
}else {
// 当前节点的左节点的最右节点
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur){
pre = pre.right;
}
if(pre.right == null){ // 第一次访问 cur
pre.right = cur;// 建立关联
cur = cur.left;
}else { // 第二次访问，打印并切断关联,且说明cur的左边都访问过了
// 打印
doubleList.addTail(cur.val);
pre.right = null;
cur = cur.right;
}
}
}
return doubleList;
}
}
/*
6
/ \
4 7
/ \ \
2 5 9
/ \ /
1 3 8
9
6 4 7
4 2 5
2 1 3
5 0 0
1 0 0
3 0 0
7 0 9
9 8 0
8 0 0
1 2 3 4 5 6 7 8 9
*/
不实用栈的中序列遍历
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class DoubleListNode{
int val;
DoubleListNode pre;
DoubleListNode next;
public DoubleListNode(int val) {
this.val = val;
pre = null;
next = null;
}
}
class DoubleList{
DoubleListNode head;
DoubleListNode tail;
public DoubleList() {
head = null;
tail = null;
}
void addTail(int val){
if(head == null){
head = new DoubleListNode(val);
tail = head;
}else {
DoubleListNode node = new DoubleListNode(val);
tail.next = node;
node.pre = tail;
tail = node;
}
}
void printList(){
if(head == null){
return;
}
boolean flag = true;
DoubleListNode p = head;
StringBuilder sb = new StringBuilder();
while (p != null){
if(flag){
sb.append(p.val);
flag = false;
}else {
sb.append(" " + p.val);
}
p = p.next;
}
System.out.println(sb.toString());
}
}
class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
left = null;
right = null;
}
}
public class Main {
public static Scanner sc = new Scanner(System.in);
public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
public static long mod = (long)Math.pow(2,29);
static List<Integer> valList = new ArrayList<>();
static Map<Integer, Integer> leftArr = new HashMap<>();
static Map<Integer, Integer> rightArr = new HashMap<>();
static TreeNode buildTree(TreeNode root, int val){
if(root == null){
root = new TreeNode(val);
}
int left = leftArr.get(val);
int right = rightArr.get(val);
if(left != 0){
root.left = buildTree(root.left, left);
}
if(right != 0){
root.right = buildTree(root.right, right);
}
return root;
}
static TreeNode buildTree(int rootVal){
Map<Integer, TreeNode> map = new HashMap<>();
for(int curVal: valList) {
map.putIfAbsent(curVal, new TreeNode(curVal));
int left = leftArr.get(curVal);
int right = rightArr.get(curVal);
if (left != 0) {
TreeNode leftNode = new TreeNode(left);
map.put(left, leftNode);
map.get(curVal).left = leftNode;
}
if (right != 0) {
TreeNode rightNode = new TreeNode(right);
map.put(right, rightNode);
map.get(curVal).right = rightNode;
}
}
return map.get(rootVal);
}
private static TreeNode createBinarySearchTree(String[] lines, int n) {
Map<Integer, TreeNode> map = new HashMap<>(n);
TreeNode root = null;
for (int i = 0; i < n; i++) {
String[] strArr = lines[i].split(" ");
int curVal = Integer.valueOf(strArr[0]);
int leftVal = Integer.valueOf(strArr[1]);
int rightVal = Integer.valueOf(strArr[2]);
map.putIfAbsent(curVal, new TreeNode(curVal));
if (leftVal != 0) {
map.put(leftVal, new TreeNode(leftVal));
map.get(curVal).left = map.get(leftVal);
}
if (rightVal != 0) {
map.put(rightVal, new TreeNode(rightVal));
map.get(curVal).right = map.get(rightVal);
}
root = root != null ? root : map.get(curVal);
}
return root;
}
// public static void main(String[] args) throws Exception {
// int n = Integer.valueOf(reader.readLine());
// int rootVal = -1;
// for (int i = 0; i < n; i++) {
// String line = reader.readLine();
// String[] strArr = line.split(" ");
// int curVal = Integer.valueOf(strArr[0]);
// int leftVal = Integer.valueOf(strArr[1]);
// int rightVal = Integer.valueOf(strArr[2]);
// leftArr.put(curVal,leftVal);
// rightArr.put(curVal, rightVal);
// if(rootVal == -1){
// rootVal = curVal;
// }
// valList.add(curVal);
// }
// TreeNode root = null;
// root = buildTree(rootVal);
// searchTree2DoubleLinkInOrder(root);
// System.out.println();
// }
public static void main(String[] args) throws Exception{
int n = Integer.valueOf(reader.readLine());
String[] lines = new String[n];
for (int i = 0; i < n; i++) {
lines[i] = reader.readLine();
}
TreeNode root = createBinarySearchTree(lines, n);
DoubleList doubleList = searchTree2DoubleLink(root);
doubleList.printList();
}
// 搜索二叉树转双向链表
static DoubleList searchTree2DoubleLink(TreeNode root){
if(root == null){
return null;
}
DoubleList doubleList = new DoubleList();
// 非递归中序遍历
TreeNode cur = root;
while (cur != null){
if (cur.left == null){
// 打印
doubleList.addTail(cur.val);
cur = cur.right;
}else {
// 当前节点的左节点的最右节点
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur){
pre = pre.right;
}
if(pre.right == null){ // 第一次访问 cur
pre.right = cur;// 建立关联
cur = cur.left;
}else { // 第二次访问，打印并切断关联,且说明cur的左边都访问过了
// 打印
doubleList.addTail(cur.val);
pre.right = null;
cur = cur.right;
}
}
}
return doubleList;
}
}
/*
6
/ \
4 7
/ \ \
2 5 9
/ \ /
1 3 8
9
6 4 7
4 2 5
2 1 3
5 0 0
1 0 0
3 0 0
7 0 9
9 8 0
8 0 0
1 2 3 4 5 6 7 8 9
*/
普通递归中序遍历
iimport java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class DoubleListNode{
int val;
DoubleListNode pre;
DoubleListNode next;
public DoubleListNode(int val) {
this.val = val;
pre = null;
next = null;
}
}
class DoubleList{
DoubleListNode head;
DoubleListNode tail;
public DoubleList() {
head = null;
tail = null;
}
void addTail(int val){
if(head == null){
head = new DoubleListNode(val);
tail = head;
}else {
DoubleListNode node = new DoubleListNode(val);
tail.next = node;
node.pre = tail;
tail = node;
}
}
void printList(){
if(head == null){
return;
}
boolean flag = true;
DoubleListNode p = head;
while (p != null){
if(flag){
System.out.print(p.val);
flag = false;
}else {
System.out.print(" " + p.val);
}
p = p.next;
}
}
}
class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
left = null;
right = null;
}
}
public class Main {
public static Scanner sc = new Scanner(System.in);
public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
public static long mod = (long)Math.pow(2,29);
static List<Integer> valList = new ArrayList<>();
static Map<Integer, Integer> leftArr = new HashMap<>();
static Map<Integer, Integer> rightArr = new HashMap<>();
static TreeNode buildTree(TreeNode root, int val){
if(root == null){
root = new TreeNode(val);
}
int left = leftArr.get(val);
int right = rightArr.get(val);
if(left != 0){
root.left = buildTree(root.left, left);
}
if(right != 0){
root.right = buildTree(root.right, right);
}
return root;
}
static TreeNode buildTree(int rootVal){
Map<Integer, TreeNode> map = new HashMap<>();
for(int curVal: valList) {
map.putIfAbsent(curVal, new TreeNode(curVal));
int left = leftArr.get(curVal);
int right = rightArr.get(curVal);
if (left != 0) {
TreeNode leftNode = new TreeNode(left);
map.put(left, leftNode);
map.get(curVal).left = leftNode;
}
if (right != 0) {
TreeNode rightNode = new TreeNode(right);
map.put(right, rightNode);
map.get(curVal).right = rightNode;
}
}
return map.get(rootVal);
}
private static TreeNode createBinarySearchTree(String[] lines, int n) {
Map<Integer, TreeNode> map = new HashMap<>(n);
TreeNode root = null;
for (int i = 0; i < n; i++) {
String[] strArr = lines[i].split(" ");
int curVal = Integer.valueOf(strArr[0]);
int leftVal = Integer.valueOf(strArr[1]);
int rightVal = Integer.valueOf(strArr[2]);
map.putIfAbsent(curVal, new TreeNode(curVal));
if (leftVal != 0) {
map.put(leftVal, new TreeNode(leftVal));
map.get(curVal).left = map.get(leftVal);
}
if (rightVal != 0) {
map.put(rightVal, new TreeNode(rightVal));
map.get(curVal).right = map.get(rightVal);
}
root = root != null ? root : map.get(curVal);
}
return root;
}
// public static void main(String[] args) throws Exception {
// int n = Integer.valueOf(reader.readLine());
// int rootVal = -1;
// for (int i = 0; i < n; i++) {
// String line = reader.readLine();
// String[] strArr = line.split(" ");
// int curVal = Integer.valueOf(strArr[0]);
// int leftVal = Integer.valueOf(strArr[1]);
// int rightVal = Integer.valueOf(strArr[2]);
// leftArr.put(curVal,leftVal);
// rightArr.put(curVal, rightVal);
// if(rootVal == -1){
// rootVal = curVal;
// }
// valList.add(curVal);
// }
// TreeNode root = null;
// root = buildTree(rootVal);
// searchTree2DoubleLinkInOrder(root);
// System.out.println();
// }
public static void main(String[] args) throws Exception{
int n = Integer.valueOf(reader.readLine());
String[] lines = new String[n];
for (int i = 0; i < n; i++) {
lines[i] = reader.readLine();
}
TreeNode root = createBinarySearchTree(lines, n);
searchTree2DoubleLinkInOrder(root);
}
static void searchTree2DoubleLinkInOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
inOrderToQueue(root, queue);
boolean flag = true;
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(flag){
sb.append(cur.val);
flag = false;
}else {
sb.append(" " + cur.val);
}
}
System.out.println(sb.toString());
}
private static void inOrderToQueue(TreeNode root, Queue<TreeNode> queue) {
if (root == null) {
return;
}
inOrderToQueue(root.left, queue);
queue.offer(root);
inOrderToQueue(root.right, queue);
}
// 搜索二叉树转双向链表
static DoubleList searchTree2DoubleLink(TreeNode root){
if(root == null){
return null;
}
DoubleList doubleList = new DoubleList();
// 非递归中序遍历
TreeNode cur = root;
while (cur != null){
if (cur.left == null){
// 打印
doubleList.addTail(cur.val);
cur = cur.right;
}else {
// 当前节点的左节点的最右节点
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur){
pre = pre.right;
}
if(pre.right == null){ // 第一次访问 cur
pre.right = cur;// 建立关联
cur = cur.left;
}else { // 第二次访问，打印并切断关联,且说明cur的左边都访问过了
// 打印
doubleList.addTail(cur.val);
pre.right = null;
cur = cur.right;
}
}
}
return doubleList;
}
}
/*
6
/ \
4 7
/ \ \
2 5 9
/ \ /
1 3 8
9
6 4 7
4 2 5
2 1 3
5 0 0
1 0 0
3 0 0
7 0 9
9 8 0
8 0 0
1 2 3 4 5 6 7 8 9
*/