| 日期 | 是否一次通过 | comment |
|---|---|---|
| 2019-05-14 20:20 | N |
将一个二叉树按照中序遍历转换成双向链表。
image.png
中序遍历
/**
* Definition for Doubly-ListNode.
* public class DoublyListNode {
* int val;
* DoublyListNode next, prev;
* DoublyListNode(int val) {
* this.val = val;
* this.next = this.prev = null;
* }
* } * Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of tree
* @return: the head of doubly list node
*/
public DoublyListNode bstToDoublyList(TreeNode root) {
// 用于保存处理过程中的双向链表的尾结点
DoublyListNode[] lastNode = new DoublyListNode[1];
convertNode(root, lastNode);
// 找到双向链表的头结点
DoublyListNode head = lastNode[0];
while (head != null && head.prev != null) {
head = head.prev;
}
return head;
}
public void convertNode(TreeNode node, DoublyListNode[] lastNode) {
// 结点不为空
if (node == null) {
return;
}
// 如果有左子树就先处理左子树
if (node.left != null) {
convertNode(node.left, lastNode);
}
// 将当前结点的前驱指向已经处理好的双向链表（由当前结点的左子树构成）的尾结点
DoublyListNode dbNode = new DoublyListNode(node.val);
dbNode.prev = lastNode[0];
// 如果左子树转换成的双向链表不为空，设置尾结点的后继
if (lastNode[0] != null) {
lastNode[0].next = dbNode;
}
// 记录当前结点为尾结点
lastNode[0] = dbNode;
// 处理右子树
if (node.right != null) {
convertNode(node.right, lastNode);
}
}
}
