美文网首页
剑指 offer 笔记 26 | 二叉搜索树与双向链表

剑指 offer 笔记 26 | 二叉搜索树与双向链表

作者: ProudLin | 来源:发表于2019-07-06 22:09 被阅读0次

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

    思路分析
    借牛客网大神的解题思路
    解题思路:
    1.将左子树构造成双链表,并返回链表头节点。
    2.定位至左子树双链表最后一个节点。
    3.如果左子树链表不为空的话,将当前root追加到左子树链表。
    4.将右子树构造成双链表,并返回链表头节点。
    5.如果右子树链表不为空的话,将该链表追加到root节点之后。
    6.根据左子树链表是否为空确定返回的节点。

    public class Solution {
    
     public TreeNode Convert(TreeNode root) {
            if(root==null)
                return null;
            if(root.left==null&&root.right==null)
                return root;
            // 1.将左子树构造成双链表,并返回链表头节点
            TreeNode left = Convert(root.left);
            TreeNode p = left;
            // 2.定位至左子树双链表最后一个节点
            while(p!=null&&p.right!=null){
                p = p.right;
            }
            // 3.如果左子树链表不为空的话,将当前root追加到左子树链表
            if(left!=null){
                p.right = root;
                root.left = p;
            }
            // 4.将右子树构造成双链表,并返回链表头节点
            TreeNode right = Convert(root.right);
            // 5.如果右子树链表不为空的话,将该链表追加到root节点之后
            if(right!=null){
                right.left = root;
                root.right = right;
            }
            return left!=null?left:root;
        }
    }
    

    https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5来源:牛客网

    相关文章

      网友评论

          本文标题:剑指 offer 笔记 26 | 二叉搜索树与双向链表

          本文链接:https://www.haomeiwen.com/subject/jawmhctx.html