LeetCode 114 Flatten Binary Tree to Linked List
概述
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
以前序顺序将二叉树变成链表。
直接法
首先前序遍历二叉树，构造相应的数组，之后再基于该数组构造对应的链表。
递归法（返回尾节点）
如何处理尾部的 base case？
class Solution {
public:
void flatten(TreeNode* root) {
helper(root);
}
TreeNode* helper(TreeNode* root) {
if (!root) return nullptr;
if (!root->left && !root->right) return root; // 这一行可以删去
auto leftTail = helper(root->left);
auto rightTail = helper(root->right);
if (leftTail) {
leftTail->right = root->right;
root->right = root->left;
} else {
root->right = root->right;
}
root->left = nullptr;
if (rightTail) return rightTail;
if (leftTail) return leftTail;
return root;
}
};
递归法（不返回尾节点）
实际上我们不需要返回尾节点也可以把右子树对应的链表拼回去，直接 while 遍历过去不就行了。
class Solution {
public:
void flatten(TreeNode* root) {
if (!root) return;
auto originRight = root->right;
flatten(root->left);
flatten(root->right);
root->right = root->left;
root->left = nullptr;
auto c = root;
while (c->right) {
c = c->right;
}
c->right = originRight;
}
};