本文共 1189 字，大约阅读时间需要 3 分钟。

题目描述

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

题目链接：

其中一个测试用例：

From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;

思路：

 根节点的处理：

这种思路类似于线索二叉树的中序遍历，只是没有标志域。

AC代码：

/**public class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }}*/public class Solution {    private TreeNode pre = null; // 因为没有二级指针，只能用全局变量了    public TreeNode Convert(TreeNode pRootOfTree) {        if (pRootOfTree == null)    return null;        if (pRootOfTree.left == null && pRootOfTree.right == null)    return pRootOfTree;        LinkedNode(pRootOfTree);        TreeNode cur = pRootOfTree;        while (cur.left != null) {            cur = cur.left;        }        return cur;    }    private void LinkedNode(TreeNode root) {        if (root.left != null) {            LinkedNode(root.left);        }        root.left = pre;        if (pre != null)    pre.right = root;        pre = root;        if (root.right != null) {            LinkedNode(root.right);        }    }}

=====================Talk is cheap, show me the code======================

转载地址：https://liuchenyang0515.blog.csdn.net/article/details/85097631 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！