LeetCode-114： 二叉树展开为链表

题目描述：

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

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

示例：

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

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

思路分析：

函数为：

void flatten(TreeNode root);

我们尝试给出这个函数的定义：

给 flatten 函数输入一个节点 root，那么以 root 为根的二叉树就会被拉平为一条链表。

我们再梳理一下，如何按题目要求把一棵树拉平成一条链表？很简单，以下流程：

1、将 root 的左子树和右子树拉平。

2、将 root 的右子树接到左子树下方，然后将整个左子树作为右子树。

上面三步看起来最难的应该是第一步对吧，如何把 root 的左右子树拉平？其实很简单，按照 flatten 函数的定义，对 root 的左右子树递归调用 flatten 函数即可：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
// 定义：将以 root 为根的树拉平为链表
    public void flatten(TreeNode root) {
        if(root==null){
            return ;
        }

        flatten(root.left);
        flatten(root.right);
 /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
        TreeNode left=root.left;
        TreeNode right=root.right;
// 2、将左子树作为右子树
        root.left=null;
        root.right=left;
 // 3、将原先的右子树接到当前右子树的末端
        TreeNode p=root;
        while(p.right!=null){
            p=p.right;
        }
        p.right=right;

    }
}

你看，这就是递归的魅力，你说 flatten 函数是怎么把左右子树拉平的？说不清楚，但是只要知道 flatten 的定义如此，相信这个定义，让 root 做它该做的事情，然后 flatten 函数就会按照定义工作。另外注意递归框架是后序遍历，因为我们要先拉平左右子树才能进行后续操作。

文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/xiewenrui1996/article/details/113899114