《剑指offer》面试题27 二叉搜索树与双向链表 Java版

(将BST改成排序的双向链表。)

我的方法一：根据BST的性质，如果我们中序遍历BST，将会得到一个从小到大排序的序列。如果我们将包含这些数字的节点连接起来，就形成了一个链表，形成双向链表也很简单。关键是我们要知道我们在准备连接一个节点时，我们要知道它之前处理的那个节点，也就是小于它的最大一个节点。如果用迭代的方法，这个信息是丢失的，所以我们要用一个变量保存这个节点。下面是中序遍历的迭代方法，处理的过程变成了连接，处理完后更新lasthandle。

        public TreeNode build(TreeNode root){
            if(root == null)return null;
            TreeNode rootMark = root;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode lasthandle = null;

            while(root != null || stack.size()>0){
                while(root != null){
                    stack.push(root);
                    root = root.left;
                }
                if(stack.size()>0){
                    root = stack.pop();

                     //开始处理
                    root.left = lasthandle;
                    if(lasthandle != null){
                        lasthandle.right = root;
                    }
                     //更新
                    lasthandle = root;

                     root = root.right;
                }
            }

            //返回头节点
            root = rootMark;
            while(root.left != null){
                root = root.left;
            }
            return root;
        }

我的方法二：也可以采用递归的方法，我们利用递归函数的返回值返回处理好的双向链表的头节点，同时利用一个lastHandle变量保存上一次处理的节点（这个值会在递归函数中更新），这样我们就可以很方便地在递归的中序遍历中进行连接操作了。（但是一直没测试通过，应该是算法出了问题）