Problem: 114. 二叉树展开为链表

题目描述

思路

思路1：借助额外空间

借助一个队列将二叉树先序遍历的节点存入，再取出连接成一个链表

思路2：后序遍历处理

后序遍历，先将左子树拉伸为一个链表，再将右子树拉伸为一个链表；最后将拉伸后的左子树接到拉伸后的右子树上

复杂度

思路1：
时间复杂度:

$O(n)$；其中$n$为二叉树节点的个数

空间复杂度:

$O(n)$

思路2：
时间复杂度:

$O(n)$；其中$n$为二叉树节点的个数

空间复杂度:

$O(height)$；其中$height$为二叉树的高度

Code

思路1：

class Solution {queue<TreeNode*> queue;
public:/*** Queue** @param root The root od a binary tree*/void flatten(TreeNode* root) {if (root == nullptr) return;preTraversal(root);while (!queue.empty()) {TreeNode* node = queue.front();queue.pop();node -> right = queue.front();}}/*** Preorder traversal** @param root The root od a binary tree*/void preTraversal(TreeNode* root) {if (root == nullptr) {return;}queue.push(root);preTraversal(root -> left);preTraversal(root -> right);}
};

思路2：

class Solution {
public:/*** Postorder traversal* * @param root*/void flatten(TreeNode *root) {if (root == nullptr) {return;}// Flatten the left and right subtreesflatten(root->left);flatten(root->right);TreeNode *left = root->left;TreeNode *right = root->right;// Treat the left subtree as the right subtreeroot->left = nullptr;root->right = left;// Connect the original right subtree to// the end of the current right subtreeTreeNode *p = root;while (p->right != nullptr) {p = p->right;}p->right = right;}
};