牛客网--二叉搜索树与双向链表

爱被打了一巴掌 2022-05-06 02:28 147阅读 0赞

附上题目连接

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

这道题有点意思，有助于理解递归，其实不用递归应该比较好点，用个队列  
就够了。  
说下我的思路，用个pre指针来记录中序遍历中结点的前驱结点，再用ppre  
保存在每个递归函数里，不然单一个pre弄不了，同时要使用node.right  
进行第二次遍历时，有得注意node.right可能被改变，所以用一个变量保存以下  
遍历完后就是结点的操作了，注意要判断ppre是node的左结点还是右节点，判断  
val即可，如果要以node.leftppre或者node.rightppre为条件会出错，比如ppre是  
node的左结点的右节点之类的情况。  
接下来贴代码吧

package 剑指offer;
    
    /**
     * Created by Administrator on 2018/10/10.
     */
    public class 二叉搜索树与双向链表 {
        private TreeNode pre=null,ret=null;
        public TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree==null)
                return pRootOfTree;
            ret=pRootOfTree;
            while (ret.left!=null){
                ret=ret.left;
            }
            inorder(pRootOfTree);
            return ret;
        }
        private void inorder(TreeNode node){
            if(node==null)
                return;
            TreeNode ppre=null,right= node.right;
            inorder(node.left);
            ppre=pre;
            pre=node;
            inorder(right);
            if(ppre==null){
                return;
            }
            if(node.val>ppre.val){
                ppre.right=node;
                node.left=ppre;
            }else{
                ppre.left=node;
                node.right=ppre;
            }
        }
    }