题解 | #二叉搜索树与双向链表# 中序遍历并连接节点

二叉搜索树与双向链表

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

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return pRootOfTree;
        }
        return merge(pRootOfTree)[0];
    }

    private TreeNode[] merge(TreeNode root) {
        // 递归终点
        if (root == null) {
            return new TreeNode[]{null, null};
        }

        // 左边链表化结果
        TreeNode[] leftPart = merge(root.left);
        
        // 右边链表化结果
        TreeNode[] rightPart = merge(root.right);

        // 连接左右两边
        if (leftPart[1] != null) {
            leftPart[1].right = root;
        }
        root.left = leftPart[1];
        root.right = rightPart[0];
        if (rightPart[0] != null) {
            rightPart[0].left = root;
        }
        
        // 返回连接后的结果[head, tail]
        TreeNode head = null;
        if (leftPart[0] != null) {
            head = leftPart[0];
        } else {
            head = root;
        }
        TreeNode tail = null;
        if (rightPart[1] != null) {
            tail = rightPart[1];
        } else {
            tail = root;
        }
        return new TreeNode[]{head, tail};
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
05-29 20:12
点赞 评论 收藏
分享
不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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