剑指Offer_26_二叉搜索树与双向链表

题目描述

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

解题思路

中序遍历就是数据递增（非递减）出现的，每次记录上一次出现的值，也即当前遍历结点的上一个结点。

实现

/*树结点的定义*/
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;
        TreeNode last = null;
        recursion(pRootOfTree, last);

        //寻找最前面的结点
        TreeNode node = pRootOfTree;
        while (node.left != null){
            node = node.left;
        }
        return node;
    }

    private TreeNode recursion(TreeNode pRootOfTree, TreeNode last) {
        if (pRootOfTree == null) return last;

        //遍历左子树
        if (pRootOfTree.left != null)
            last = recursion(pRootOfTree.left,last);

        //调整当前结点
        pRootOfTree.left = last;
        if (last != null)
            last.right = pRootOfTree;
        last = pRootOfTree;

        //遍历右子树
        if (pRootOfTree.right != null)
            last = recursion(pRootOfTree.right,last);

        return last;
    }
}