二叉树结构

  1. class TreeNode {
  2. int val = 0;
  3. TreeNode left = null;
  4. TreeNode right = null;
  5. public TreeNode(int val) {
  6. this.val = val;
  7. }
  8. }

题目描述

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

思路:

  1. 由于二叉搜索树的中序遍历就是排序的,如果是构造单链表,只需要一次中序遍历就可以了
  2. 但现在需要构造双链表,也就是在中序遍历的过程中需要设置每个结点的left与right指针,现在问题是如何设置这两个指针
  3. 二叉搜索树有一个特点,就是根结点的左子树上所有结点都比根结点的值小,而右子树上的所有结点的值都比根结点的值大
  4. 利用这个性质,当遍历根结点的左孩子的时候,可以继续把其当做左子树的根结点,右孩子可以当做右子树的根结点,从而使用递归完成

步骤

  • 以左子树为例,依次访问结点的左孩子,当遍历到叶子节点的时候,递归结束,并把该叶子结点设为左子树转换的双链表的第一个结点
  • 然后把其父结点链在其右边,设置left和right指针;如果父结点有右孩子,则继续对其右孩子继续转换,链在父结点的右边(父结点的右孩子肯定比父结点大)
  • 这样当左右子树都转换完成后,返回双链表的第一个结点就可以了

代码实现

  1. public TreeNode convert(TreeNode pRootOfTree) {
  2. if(pRootOfTree == null){
  3. return null;
  4. }
  5. if(pRootOfTree.left == null && pRootOfTree.right == null){
  6. return pRootOfTree;
  7. }
  8. TreeNode pLastNodeOfLeftList = convert(pRootOfTree.left);
  9. TreeNode p = pLastNodeOfLeftList;
  10. //定位到左子树双链表的最后一个结点
  11. while(p != null && p.right != null){
  12. p = p.right;
  13. }
  14. //将root结点追加到左子树双链表的最后一个结点
  15. if(pLastNodeOfLeftList != null){
  16. p.right = pRootOfTree;
  17. pRootOfTree.left = p;
  18. }
  19. //转换右子树为双链表
  20. TreeNode pLastNodeOfRightList = convert(pRootOfTree.right);
  21. //将root追加至右子树双链表的最后一个结点
  22. if(pLastNodeOfRightList != null){
  23. pLastNodeOfRightList.left = pRootOfTree;
  24. pRootOfTree.right = pLastNodeOfRightList;
  25. }
  26. //返回左子树的第一个结点
  27. if(pLastNodeOfLeftList != null){
  28. return pLastNodeOfLeftList;
  29. }
  30. return pRootOfTree;
  31. }