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

二叉搜索树与双向链表

https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5

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

全部评论

相关推荐

07-09 19:25
门头沟学院 Java
这是要把每一个投校招的都开盒吗?
26届之耻将大局逆转:裁人的时候一次性追回餐费
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 10:39
一个证都没&nbsp;我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
星辰再现:裁员给校招生腾地方
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务