当前位置:  首页>> 技术小册>> 数据结构与算法(下)

题目描述

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

解法

由于是二叉搜索树,因此中序遍历的结果就是排序的。

中序遍历利用栈来实现。遍历时,前一个结点的 right 指向后一个结点,后一个结点的 left 指向前一个结点。

  1. pre.right = cur
  2. cur.left = pre
  1. import java.util.Stack;
  2. /**
  3. * @author bingo
  4. * @since 2018/11/24
  5. */
  6. /**
  7. public class TreeNode {
  8. int val = 0;
  9. TreeNode left = null;
  10. TreeNode right = null;
  11. public TreeNode(int val) {
  12. this.val = val;
  13. }
  14. }
  15. */
  16. public class Solution {
  17. /**
  18. * 将二叉搜索树转换为双向链表
  19. *
  20. * @param pRootOfTree
  21. * @return
  22. */
  23. public TreeNode Convert(TreeNode pRootOfTree) {
  24. if (pRootOfTree == null) {
  25. return null;
  26. }
  27. Stack<TreeNode> stack = new Stack<>();
  28. TreeNode cur = pRootOfTree;
  29. TreeNode res = null;
  30. TreeNode pre = null;
  31. while (cur != null || !stack.isEmpty()) {
  32. if (cur != null) {
  33. stack.push(cur);
  34. cur = cur.left;
  35. } else {
  36. cur = stack.pop();
  37. if (pre == null) {
  38. pre = cur;
  39. res = pre;
  40. } else {
  41. pre.right = cur;
  42. cur.left = pre;
  43. pre = cur;
  44. }
  45. cur = cur.right;
  46. }
  47. }
  48. return res;
  49. }
  50. }

测试用例

  1. 功能测试(输入的二叉树是完全二叉树;所有结点都没有左/右子树;只有一个结点的二叉树);
  2. 特殊输入测试(指向二叉树根结点的指针为空指针)。

该分类下的相关小册推荐: