《剑指Offer》-36.二叉搜索树与双向链表

题干

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的方向。比如，输入如图的二叉搜索树，则输出转换之后的排序双向链表。二叉搜索树节点定义如下：

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
}

二叉搜索树

graph TD
10-->6
10-->14
6-->4
6-->8
14-->12
14-->16

排序双向链表

graph LR
4-->6
6-->4
6-->8
8-->6
8-->10
10-->8
10-->12
12-->10
12-->14
14-->12
14-->16
16-->14

解题思路

由于需要排好序的链表，所以需要中序遍历二叉搜索树。

将原先指向左子节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。将二叉搜索树看出3部分，根节点、左子树和右子树。在把左、右子树都转换成排序双向链表之后再和根节点链接起来，整棵二叉搜索树就转换成了排序双向链表。

代码实现

<?php

class TreeNode
{
    private $val;
    private $left;
    private $right;

    public function __set($name, $value)
    {
        $this->$name = $value;
    }

    public function __get($name)
    {
        return $this->$name;
    }
}

function getTree()
{
    $node1 = new TreeNode();
    $node1->val = 10;
    $node2 = new TreeNode();
    $node2->val = 6;
    $node3 = new TreeNode();
    $node3->val = 14;
    $node1->left = $node2;
    $node1->right = $node3;
    $node4 = new TreeNode();
    $node4->val = 4;
    $node5 = new TreeNode();
    $node5->val = 8;
    $node2->left = $node4;
    $node2->right = $node5;
    $node6 = new TreeNode();
    $node6->val = 12;
    $node7 = new TreeNode();
    $node7->val = 16;
    $node3->left = $node6;
    $node3->right = $node7;

    return $node1;
}

function Convert($root)
{
    $lastInList = null;
    ConvertNode($root, $lastInList);

    $head = $lastInList;
    while ($head != null && $head->left != null) {
        $head = $head->left;
    }

    return $head;
}

function ConvertNode($root, &$lastInList)
{
    if ($root == null) {
        return;
    }
    $current = $root;
    if ($current->left != null) {
        ConvertNode($current->left, $lastInList);
    }

    $current->left = $lastInList;
    if ($lastInList != null) {
        $lastInList->right = $current;
    }
    $lastInList = $current;
    if ($current->right != null) {
        ConvertNode($current->right, $lastInList);
    }
}

function printList($head)
{
    $last = $head;
    while ($head != null) {
        echo $head->val.' ';
        $head = $head->right;
        if ($head != null) {
            $last = $head;
        }
    }
    echo PHP_EOL;
    while ($last != null) {
        echo $last->val.' ';
        $last = $last->left;
    }
}

printList(Convert(getTree()));