二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

示例

分析

根据二叉树搜索树的特点可知，根节点的左子树都比它小，右子树都比它大。所以要转换成一个排序的双向链表，就按照左 → 中 → 右的顺序连接起来，而这个顺序恰好是中序遍历。

1. 递归左子树，找到最左（最小值）的节点tail，并作为双向链表的链表头head。
2. 将tail与其父节点双向连接起来，再判断父节点是否有右节点，有的话递归右节点的左节点，没有的话则连接右节点。

代码

// 树节点
class TreeNode
{
    var $val;
    var $left = NULL;
    var $right = NULL;

    public function __construct($val){
        $this->val = $val;
    }
}

<?php

namespace app\index\controller;

class Index
{
    /**
     * 二叉搜索树转换成一个排序的双向链表
     * @param object $pRootOfTree 根节点
     */
    public function Convert($pRootOfTree)
    {
        if ($pRootOfTree == NULL) return;

        $head = null;  // head 是双向链表的头结点
        $tail = null;  // tail 是指针节点
        $this->recursive($pRootOfTree, $head, $tail);  // 调用递归函数 
        return $head;  // 返回头结点
    }

    /**
     * 中序遍历
     */
    function recursive($pRootOfTree, &$head, &$tail)
    {
        if ($pRootOfTree == NULL) return;

        $this->recursive($pRootOfTree->left, $head, $tail);  // 递归左子树，找到最小节点

        if ($head == NULL) {                                 // 如果是第一次找到最小值
            $head = $tail = $pRootOfTree;
        } else {                                             // 如果已经有头结点了，按中序遍历连接节点
            $tail->right       = $pRootOfTree;
            $pRootOfTree->left = $tail;
            $tail              = $pRootOfTree;
        }

        $this->recursive($pRootOfTree->right, $head, $tail);  // 递归父节点的右节点
    }
}

测试

<?php

namespace app\index\controller;

class Test
{
    /**
     * 测试
     */
    public function test()
    {
        // 构造二叉搜索树
        $pRootOfTree        = new TreeNode(7);
        $node1              = new TreeNode(1);
        $node2              = new TreeNode(13);
        $node3              = new TreeNode(11);
        $node4              = new TreeNode(10);
        $pRootOfTree->left  = $node1;
        $pRootOfTree->right = $node2;
        $node2->left        = $node3;
        $node3->left        = $node4;

        $list = $this->Convert($pRootOfTree);  // 调用
        print_r($list);
    }
}