253.LeetCode | 114. 二叉树展开为链表

vlambda
2021-03-06

253.LeetCode | 114. 二叉树展开为链表

每天一个开发小知识

题目

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

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

解法一：前序遍历

通过前序遍历将树的所有节点保存到数组中

然后

将数组中的节点构造成一颗只有右子树的树

时间复杂度 O(n)，空间复杂度 O(n)

/** * 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) { vector<TreeNode*> vec; Do(root, vec);
 for (int i = 1; i < vec.size(); ++i) { vec[i - 1]->left = NULL; vec[i - 1]->right = vec[i]; } }
    void Do(TreeNode * node, vector<TreeNode*> & vec) { if (NULL == node) { return; }
 vec.push_back(node); Do(node->left, vec); Do(node->right, vec); }};

解法二：递归 + 乾坤大挪移

由于最终的树是按前序遍历排列

所以

一个节点的右子树一定挂在左子树中最大的那个节点上

首先，通过递归找到当前节点的左子树中最大节点

然后，将当前节点的右子树作为当前节点的左子树最大节点的右子树（乾坤大挪移）

再然后，将当前节点的左子树移到当前节点的右边

最后，将当前节点的左子树置空

时间复杂度 O(n)，空间复杂度 O(n)

/** * 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 * p = root; while (NULL != p) { if (NULL != p->left) { TreeNode * left_max = Do(p->left); left_max->right = p->right; p->right = p->left; p->left = NULL; } p = p->right; } }
 TreeNode * Do(TreeNode * node) { if (NULL == node->left && NULL == node->right) { return node; }
 if (NULL != node->right) { return Do(node->right); } else { return Do(node->left); } }};