剑指offer_8_二叉树转双链表

• 2019 年 10 月 7 日
• 筆記

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

思路：根据二叉树的中序遍历为有序的特性，我们只需要在其中序遍历的递归函数里改变指向就可以啦。

public class Reverse {      TreeNode pre = null;      TreeNode head = null;        public TreeNode change(TreeNode root) {          deal(root);          return head;      }        public void deal(TreeNode node) {          deal(node.left);          // 当前节点的左指针指向上一个节点          node.left = pre;          // 上一个节点的右指针指向下一个节点          if (pre != null) {              pre.right = node;          }          // 将当前节点置为"上一个节点"给后续节点使用          pre = node;          if (head == null) {              head = node;          }          // 递归右节点          deal(node.right);      }  }

总结：利用好二叉树各种遍历的特性，完美解决。