题解 | #二叉搜索树与双向链表#

<?php
/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/
function Convert($pRootOfTree)
{
    if($pRootOfTree == null){
        return null;
    }
    $pre = null;
    inOrder($pRootOfTree, $pre);
    $ret = $pRootOfTree;
    while($ret != null && $ret->left != null){
        $ret = $ret->left;
    }
    return $ret;
}

// 中序遍历
function inOrder($root, &$prev){
    if($root==null){
        return;
    }
    inOrder($root->left, $prev);
    // 当前左边指向上一个
    $root->left = $prev;
    // 上一个的右边指向当前
    if($prev != null){
        $prev->right = $root;
    }
    $prev = $root;
    inOrder($root->right, $prev);
}

二叉搜索树：左边不空的话，左边的节点全<根，右边不空的话，右边的全大于根

最适用于：中序遍历

原理：每个节点的left指向上一个，right指向下一个

方法：递归中序遍历，维护一个prev指针记录上个节点。注意：prev需要传实参才能记录真实的上一个节点。

inOrder(root->left,prev);

curr->left指向左

prev->right指向右（代替curr->right指向next，因为我们不知道下一个是什么，还没有遍历到）

prev移动到curr

inOrder(root->right, prev)