博文中会简要介绍Leetcode P0114题目分析及解题思路。
“Flatten Binary Tree to Linked List”其实是一个前序遍历的变形题。主要思路还是深度优先搜索，这里既可以采取递归回溯的西路，也可以采取DFS的探索思路。第二种解法用C++实现比较方便，故写在C++代码中。
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1 / \ 2 5 / \ \ 3 4 6The flattened tree should look like:
1 \ 2 \ 3 \ 4 \ 5 \ 6
这里主要介绍递归回溯的思路。递归回溯的思路的核心在于，平面化（flatten）后某个树结点的右指针指向其原先的左子树平面化后的链表。也就是说，对于递归函数而言，对左子树，每次至少要返回其平面化后的链表的头结点，然后当前树结点的右指针将指向这个头结点。
而对于某个树结点的右子树，其平面化的链表将连在这个树结点左子树的平面化后的链表后面。也就是说，对于这个树结点而言，其递归函数平面化左子树后，不仅要返回链表头结点，也要返回链表尾结点。而尾结点则一定是这棵左子树最上层的右叶子结点（如果存在）或者这棵左子树的最下层左结点。
根据以上想法，我们就可以设计递归回溯函数，将返回值设置为一个数组，返回平面化后的链表的头结点和尾结点。
以下是Java的题解代码实现。
/**
* 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) {
if (root == null)
return;
this.flatten2(root);
}
private TreeNode[] flatten2(TreeNode curr) {
if (curr.left == null && curr.right == null)
return new TreeNode[] {curr, curr};
TreeNode right = curr.right, end = curr;
if (curr.left != null) {
TreeNode[] startAndEnd = this.flatten2(curr.left);
curr.right = startAndEnd[0];
end = startAndEnd[1];
}
curr.left = null;
if (right != null) {
TreeNode[] startAndEnd = this.flatten2(right);
end.right = startAndEnd[0];
end = startAndEnd[1];
}
return new TreeNode[] {curr, end};
}
}
以下是C++的题解代码实现，下述解法更趋近于递归回溯的思路。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
if (!root)
return;
this->_flatten(root);
}
private:
vector<TreeNode*> _flatten(TreeNode *curr) {
if (!curr->left && !curr->right)
return {curr, curr};
TreeNode *right = curr->right, *end = curr;
if (curr->left) {
vector<TreeNode*> start_end = this->_flatten(curr->left);
curr->right = start_end[0];
end = start_end[1];
}
curr->left = NULL;
if (right) {
vector<TreeNode*> start_end = this->_flatten(right);
end->right = start_end[0];
end = start_end[1];
}
return {curr, end};
}
};
以下是C++解法的第二种代码实现，下述代码更趋近DFS的思路，通过不断地下移parent指针来保证parent始终指向当前链表末尾的非空指针。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode *dummy = new TreeNode(0);
this->_flatten(dummy, root);
}
private:
void _flatten(TreeNode *&parent, TreeNode *curr) {
if (!curr)
return;
// 记录右子树
TreeNode *right = curr->right;
// 后移parent，保持在非空尾指针
parent->right = curr;
parent = parent->right;
if (curr->left)
this->_flatten(parent, curr->left);
curr->left = NULL;
if (right)
this->_flatten(parent, right);
}
};