剑指offer 26.二叉搜索树与双向链表

26.二叉搜索树与双向链表

题目

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

思路

二叉树还是要递归方法，对于每个节点，若为空直接返回，不然就递归到子节点。这里和正常的不一样，先寻找右节点，然后在找左节点，可以省下来一个存储位。

代码

 public class TreeNode {

  int val = 0;
  TreeNode left = null;
  TreeNode right = null;

  public TreeNode(int val) {
    this.val = val;
  }
}

TreeNode ans = null;

public TreeNode Convert(TreeNode pRootOfTree) {
  if (pRootOfTree == null) {
    return pRootOfTree;
  }
  Convert(pRootOfTree.right);
  if (ans == null) {
    ans = pRootOfTree;
  } else {
    ans.left = pRootOfTree;
    pRootOfTree.right = ans;
    ans = pRootOfTree;
  }
  Convert(pRootOfTree.left);
  return ans;
}