【1错-1】 将二叉树转换成双链表

https://www.lintcode.com/problem/convert-binary-tree-to-doubly-linked-list/description?_from=ladder&&fromId=6

将一个二叉树按照中序遍历转换成双向链表。

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);
        }
    }
}