二叉搜索树与双向链表

描述

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

思路

代码

1. 中序遍历 + 分治 + 递归，每个分治部分返回链表的头结点，所以要移动到左边链表的最后结点再和根结点连接，右链表头结点直接和根结点连接

/**
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 root) {
        if (root == null) {
            return null;
        }
        
        if (root.left == null && root.right == null) {
            return root;
        }
        
        TreeNode left = Convert(root.left);
        TreeNode node = left;
        while (node != null && node.right != null) {
            node = node.right;
        }
        if (left != null) {
            node.right = root;
            root.left = node;
        }
        TreeNode right = Convert(root.right);
        if (right != null) {
            right.left = root;
            root.right = right;
        }
        
        return left == null ? root : left;
    }
}

2. 中序遍历 + 非递归

import java.util.*;
/**
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 root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        TreeNode preNode = null;
        TreeNode FirstNode = null;
        boolean isFirst = true;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        
            node = stack.pop();
            if (isFirst) {
                FirstNode = node;
                preNode = node;
                isFirst = false;
            } else {
                node.left = preNode;
                preNode.right = node;
                preNode = node;
            }
            node = node.right;
        }
        
        return FirstNode;
    }
}