-
Notifications
You must be signed in to change notification settings - Fork 149
Expand file tree
/
Copy pathBinaryToLinked27.java
More file actions
62 lines (57 loc) · 1.69 KB
/
BinaryToLinked27.java
File metadata and controls
62 lines (57 loc) · 1.69 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package com.so;
/**
* 第27题
* 将二叉搜索树转换成一个排序的双向链表
*
* @author qgl
* @date 2017/08/14
*/
public class BinaryToLinked27 {
/**
* 二叉树
*/
static class BinaryTreeNode {
int data;
BinaryTreeNode leftNode;
BinaryTreeNode rightNode;
}
/**
* 二叉树的转换
* @param root
* @return
*/
public static BinaryTreeNode convert(BinaryTreeNode root) {
//指向双向链表的尾节点
BinaryTreeNode lastNode = convertNode(root, null);
//找到转换后的链表的头节点
BinaryTreeNode pHead = lastNode;
while (pHead != null && pHead.leftNode != null) {
pHead = pHead.leftNode;
}
//返回链表头节点
return pHead;
}
public static BinaryTreeNode convertNode(BinaryTreeNode root, BinaryTreeNode lastNode) {
if (root == null) {
return null;
}
BinaryTreeNode current = root;
//递归处理左子树
if (current.leftNode != null) {
lastNode = convertNode(current.leftNode, lastNode);
}
//将当前节点的左指针指向已经转换好的链表的最后一个位置
current.leftNode = lastNode;
//将已经转换好的链表的最后一个节点的右指针指向当前节点
if (lastNode != null) {
lastNode.rightNode = current;
}
//更新已经转换好的链表的最后一个节点
lastNode = current;
//递归处理右子树
if (current.rightNode != null) {
lastNode = convertNode(current.rightNode, lastNode);
}
return lastNode;
}
}