【Leetcode 热题 100】114. 二叉树展开为链表

问题背景

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

数据约束

• 树中结点数在范围 $[0,2000]$ 内
• $-100\le Node.val\le 100$

解题过程

可以从尾到头构建链表，那么要求递归的顺序与先序遍历恰好相反，先递归遍历右子树，再递归遍历左子树，最后处理当前节点。当前节点应该用头插法加入到链表中，需要一个变量来保存先前处理完的节点。
从分治的观点来看，每棵子树可以把根节点作为划分标准，拆成左右子树两个不同的部分。这时构造链表只需要将左右子树上已经形成的链表串起来即可。

具体实现

直接递归

/*** 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 {private TreeNode pre;public void flatten(TreeNode root) {if(root == null) {return;}flatten(root.right); // 递归处理左子树flatten(root.left); // 递归处理右子树root.left = null; // 根节点的左指针域置空root.right = pre; // 根节点的右指针域指向先前保存的节点pre = root; // 重新记录}
}

分治合并

/*** 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 {public void flatten(TreeNode root) {dfs(root);}// 递归方法返回每棵子树的尾节点private TreeNode dfs(TreeNode root) {if(root == null) {return null;}TreeNode leftTail = dfs(root.left); // 递归获取左子树的尾节点TreeNode rightTail = dfs(root.right); // 递归获取右子树的尾节点if(leftTail != null) {leftTail.right = root.right; // 左子树的尾节点右指针域指向右子树root.right = root.left; // 根节点的右指针域指向左子树root.left = null; // 根节点的左子树置空}// 维持方法定义，按照右左根的优先顺序返回子树的尾节点return rightTail != null ? rightTail : leftTail != null ? leftTail : root;}
}