題干

輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的節(jié)點，只能調(diào)整樹中節(jié)點指針的方向。比如，輸入如圖的二叉搜索樹，則輸出轉(zhuǎn)換之后的排序雙向鏈表。二叉搜索樹節(jié)點定義如下：

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

解題思路

由于需要排好序的鏈表，所以需要中序遍歷二叉搜索樹。

將原先指向左子節(jié)點的指針調(diào)整為鏈表中指向前一個節(jié)點的指針，原先指向右子節(jié)點的指針調(diào)整為鏈表中指向后一個節(jié)點的指針。將二叉搜索樹看出3部分，根節(jié)點、左子樹和右子樹。在把左、右子樹都轉(zhuǎn)換成排序雙向鏈表之后再和根節(jié)點鏈接起來，整棵二叉搜索樹就轉(zhuǎn)換成了排序雙向鏈表。

代碼實現(xiàn)

<?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()));