剑指offer36.二叉搜索树BST转换成双向链表P191

剑指offer36. 二叉搜索树BST转换成双向链表P191

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

C++

首先，牵扯到排序，就只能对BST中序遍历（这也是下面递归函数的模板）。另外，双向链表有左右两个指针，二叉树刚好左右两指针，通过对比显然可以用二叉树的left指针充当链表前驱指针，right指针充当后继指针。至于为什么要在递归函数中多一个lastnode，是因为一次指针变更操作，（除了涉及空节点的）操作节点一定是两个（一个指针指向另一个节点），所以需要给当前递归的操作节点显式地指明它的前驱或者后继。

BinaryTreeNode *convert(BinaryTreeNode *proot) { if (proot == NULL) return NULL; BinaryTreeNode *lastNode = NULL; // 前驱节点，最左叶节点前驱是NULL preOrderConvert(proot, &lastNode); // 递归转换 // 最后递归结束，lastnode指向的是链表的最右节点，但是应该返回最左的头结点 //书上多一个判lastnode空，因为在书上函数开始没有判空 while (lastNode -> m_pLeft != NULL) { lastNode = lastNode -> m_pLeft; } return lastNode; // 返回双向链表左头节点 } void preOrderConvert(BinaryTreeNode *root, BinaryTreeNode **lastNode) { if (root == NULL) return; // 递归出口 if (root -> m_pLeft != NULL) // 左递归 preOrderConvert(root -> m_pLeft, lastNode); root -> m_pLeft = *lastNode; // 当前节点前驱指针指向前驱节点 if ((*lastNode) != NULL) { // 前驱节点不是空，前驱的后继节点指向当前节点 (*lastNode) -> m_pRight = root; // 只有root是最左叶节点才不执行，没有前驱 } (*lastNode) = root; // 更新前驱节点 if (root -> m_pRight != NULL) // 右递归 preOrderConvert(root -> m_pRight, lastNode); }

Java

public class Solution { TreeNode pre = null; // 当前节点的前驱 public TreeNode Convert(TreeNode root) { if (root == null) return null; helper(root); while (root.left != null) root = root.left; return root; } void helper(TreeNode root) { if (root == null) return; helper(root.left); if (pre != null) { pre.right = root; } root.left = pre; pre = root; helper(root.right); } }