剑指offer_二叉树---二叉搜索树与双向链表

/**
 * 
 */
package 二叉树;
/**
 * <p>
 * Title:输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
 * </p>
 * 解题思路： 1.将左子树构造成双链表，并返回链表头节点。 2.定位至左子树双链表最后一个节点。
 * 3.如果左子树链表不为空的话，将当前root追加到左子树链表。 4.将右子树构造成双链表，并返回链表头节点。
 * 5.如果右子树链表不为空的话，将该链表追加到root节点之后。 6.根据左子树链表是否为空确定返回的节点。
 * <p>由于要求转换后是排好序的，所以采用中序遍历。
 * Description:
 * </p>
 * 
 * @author 田茂林
 * @data 2017年8月8日 下午10:36:03
 */
public class Convert {
  public TreeNode NodeConvert(TreeNode root) {
    if (root == null)
      return null;
    if (root.left == null && root.right == null)
      return root;
    //中序遍历哦==========================================================
    // 1.将左子树构造成双链表，并返回链表头节点
    TreeNode left = NodeConvert(root.left);  
    TreeNode p = left;
    // 2.定位至左子树双链表最后一个节点
    while (p != null && p.right != null) {
      p = p.right;
    }
    // 3.如果左子树链表不为空的话，将当前root追加到左子树链表
    if (left != null) {
      p.right = root;
      root.left = p;
    }
    //中序遍历哦==========================================================
    // 4.将右子树构造成双链表，并返回链表头节点
    TreeNode right = NodeConvert(root.right);
    // 5.如果右子树链表不为空的话，将该链表追加到root节点之后
    if (right != null) {
      right.left = root;
      root.right = right;
    }
    return left != null ? left : root;
  }
}