题目描述

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

双向链表：它的每个数据结点中都有两个 ，分别指向直接后继和直接前驱

Solution 1:

public class Solution {

    TreeNode realhead = null; //realhead 是双向链表的头

    TreeNode cur = null;

    public TreeNode Convert(TreeNode pRootOfTree) {

        convertSub(pRootOfTree);

        return realhead;

    }

    

    private void convertSub(TreeNode pRootOfTree) {

        if (pRootOfTree == null)

            return;

        convertSub(pRootOfTree.left);

        if (realhead == null) {

            cur = pRootOfTree; //把最左的节点赋给cur和realhead，只在最开始链表没数据时会进入这个if语                                                   句

            realhead = pRootOfTree;

        } else {

            cur.right = pRootOfTree; //双向链表，所以必须得对左右声明赋值

            pRootOfTree.left = cur;

            cur = pRootOfTree; //把该节点设成新的head

        }

        convertSub(pRootOfTree.right);

    }

}

Solution 2: //借助stack

public class Solution {

    public TreeNode Convert(TreeNode root) {

        if (root == null)

            return null;

        Stack<TreeNode> stack = new Stack<>();

        TreeNode pre = null; //用于保存中序遍历的上一节点

        boolean isFirst = true;

        stack.push(root);

        while (!stack.isEmpty()) { 

            TreeNode p = stack.peek();

            while (p != null) {

                p = p.left;

                stack.push(p);

            }

            stack.pop();

            if (!stack.isEmpty()) {

                p = stack.pop();

                if (isFirst) {//只在最开始链表没数据时会进入这个if语句

                    root = p;

                    pre = p;

                    isFirst = false;

                } else {

                    pre.right = p;

                    p.left = pre;

                    pre = p;

                }

                stack.push(p.right);

            }

        }

        return root;

    }

}