LeetCode刷题【面试题17.12】BiNode

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意：本题相对原题稍作改动

示例：

输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]

提示：

• 节点数量不会超过 100000。

题解

很明显，二叉搜索树转换成的是有序递增链表，直接用DFS中序遍历处理。

需要两个变量，一个用来记录一开始访问到的新的头结点位置，另一个用来记录在DFS过程中上次遍历到的节点，及该节点的前驱节点。

按照题目的要求，在遍历过程中重新指向节点之间新的left、right指向关系，而不重新生成新的节点。

另外，最后记得清空下最后的节点的左右子节点

current.left = null;
current.right = null;

当二叉树的右子树最末端是这样的情况的时候

       …
         \
          5
         /
        4

4节点先被加入到节点结尾，4节点的left被指向null，right指向到5。

5节点最后被加入到结尾，此时5的left还是指向到4，需要再去清除下关系。

当然可以在dfs中处理一下也是可以的。

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private TreeNode head;
    private TreeNode current;
    public TreeNode convertBiNode(TreeNode root) {
        if (null == root)return null;
        dfs(root);
        current.left = null;
        current.right = null;
        return head;
    }

    private void dfs(TreeNode root){
        if (root.left!=null){
            dfs(root.left);
        }
        if (head ==null){
            head = root;
        }
        if (current!=null){
            current.left = null;
            current.right = root;
        }
        current = root;
        if (root.right!=null){
            dfs(root.right);
        }
    }


}
//leetcode submit region end(Prohibit modification and deletion)