题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
其中一个测试用例：
{10,6,14,4,8,12,16}（按层序遍历输入）
对应输出应该为:
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======================
京公网安备 11010502036488号