635，二叉树展开为链表，多种方式解决

Original 博哥数据结构和算法 2022-05-10

问题描述

来源：LeetCode第114题

难度：中等

给你二叉树的根结点root，请你将它展开为一个单链表：

展开后的单链表应该同样使用TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。
展开后的单链表应该与二叉树先序遍历顺序相同。

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

重建二叉树

题中说了把二叉树转化为单链表，这里说的单链表是指二叉树所有节点的左子节点全部为空。并且这个单链表与二叉树的前序遍历顺序相同。所以最容易想到的一种解决方式就是通过前序遍历的方式获取二叉树的所有节点，然后在重新构造二叉树。原理很简单，我们来看下代码。

public void flatten(TreeNode root) {
    List<TreeNode> list = new ArrayList<>();
    //获取二叉树前序遍历的节点
    preorderTraversal(root, list);
    //如果二叉树是空，直接返回
    if (list.size() == 0)
        return;

    //重新构造二叉树
    TreeNode parent = root;
    for (int i = 1; i < list.size(); i++) {
        parent.right = list.get(i);
        parent.left = null;//左子节点为空
        parent = parent.right;
    }
}

//通过前序遍历获取二叉树的节点
public void preorderTraversal(TreeNode root, List<TreeNode> list) {
    if (root == null)
        return;
    list.add(root);
    preorderTraversal(root.left, list);//递归左子节点
    preorderTraversal(root.right, list);//递归右子节点
}

参考Morris遍历

在前面我讲过488，二叉树的Morris中序和前序遍历，他是找到当前节点的左子节点的最右节点，然后让这个最右节点的右指针指向当前节点。如果对Morris遍历不熟悉的话可能感觉有点绕，但没关系，我们画个图来看一下

这里我们找到最右节点之后：

直接让当前节点的右子节点成为最右节点的右子节点
然后让当前节点的左子节点变成当前节点的右子节点
接着再把当前节点的左子节点变为空
重复上面的过程，直到所有节点都访问完成……

按照上面的步骤即可，我们画个图来看一下

最后在来看下代码

public void flatten(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        TreeNode left = cur.left;
        //判断左子节点是否为空
        if (left != null) {
            //找到pre节点，他是左子节点的最
            //右节点(如果左子节点有右子节点)，
            //否则他就是左子节点
            TreeNode pre = left;
            while (pre.right != null)
                pre = pre.right;
            //把当前节点的右子节点挂到pre节点的右边
            pre.right = cur.right;
            //把当前节点的左子节点变为右子节点
            cur.right = left;
            //最后再把当前节点的左子节点设置为空
            cur.left = null;
        }
        //继续下一个节点
        cur = cur.right;
    }
}

递归方式解决

我们可以通过递归的方式先展开左子节点然后在展开右子节点，最后在合并即可。合并的原则是让当前右子节点成为当前左子节点最后一个节点的右子节点，然后让当前左子节点成为当前右子节点，同时当前左子节点变为空，画个图看一下

看下代码，注意这里是先把左子节点变为右子节点之后，再把原来的右子节点连接到最下面

public void flatten(TreeNode root) {
    if (root == null)
        return;
    flatten(root.left);//展开左子节点
    flatten(root.right);//展开右子节点

    //记录下当前节点的右子节点
    TreeNode right = root.right;
    //把当前节点的左子节点变为右子节点
    root.right = root.left;
    //然后把左子节点变为空
    root.left = null;

    //找到原来左子节点（也就是现在的右子节点）
    //的最后一个节点，让之前记录下的右子节点
    //成为他的右子节点
    TreeNode last = root;
    while (last.right != null)
        last = last.right;
    last.right = right;
}

这里每次左右子节点连接的时候我们都要先找出左子节点的最后一个节点，有点麻烦，那么能不能不需要查找呢。其实有一种方式是可以的，我们知道二叉树的后续遍历顺序是

左子节点→右子节点→当前节点

上面递归我们先遍历的是左子节点，当左子节点遍历完的时候，我们已经不记得展开之后的最后一个节点了，所以需要查找。我们来看一个图

比如当前节点是1，如果先展开节点1的右子节点，展开之后让他成为节点5的右子节点，那么节点5展开之后让他成为节点4的右子节点……按照这样一个顺序，我们会发现他和二叉树的后续遍历比较相似，他的遍历顺序就是

右子节点→左子节点→当前节点

搞懂了这个，代码就容易了，最后我们来看下

//需要挂到当前节点的右子节点，也就是访问
//之后的节点展开的二叉树的根节点
private TreeNode right = null;

public void flatten(TreeNode root) {
    if (root == null)
        return;
    //先展开右子节点（注意顺序，先右后左）
    flatten(root.right);
    //在展开左子节点
    flatten(root.left);
    //让right成为当前节点的右子节点
    root.right = right;
    //把当前的左子节点变为空
    root.left = null;
    //更新right的值
    right = root;
}