Halo

A magic place for coding

0%

LeetCode解题报告(375) -- 114. Flatten Binary Tree to Linked List

Problem

Given the root of a binary tree, flatten the tree into a “linked list”:

  • The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
  • The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Example1

1
2
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

1
2
Input: root = []
Output: []

Example 3:

1
2
Input: root = [0]
Output: [0]

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?


Analysis

  题目要求把一个二叉树打平成一条链表,顺序按照前序遍历的结果。最简单的做法就是先前序遍历一遍,把结果存到一个数组中,最后再从数组中重新构建一条链表。但是题目的Follow up要求的时候不使用额外的空间,意味着要通过操作二叉树的节点来打平成链表。

  首先,对于某一个节点来说,前序遍历的顺序是自己->左子树->右子树,所以如果要打平成链表的话,就要把左子树移动到右子树之前。我们首先要找到最左的叶子结点,然后,把这个节点作为其父节点的右节点,原来的右节点作为这个新右节点的右节点。对于二叉树的操作递归进行即可。


Solution

  无


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 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;
if (root->left) flatten(root->left);
if (root->right) flatten(root->right);
TreeNode *tmp = root->right;
root->right = root->left;
root->left = NULL;
while (root->right) root = root->right;
root->right = tmp;
}
};

Summary

  这道题目是二叉树题目中比较经典的题目。难度中等,主要还是考察前序遍历的特点。处理方法上二叉树问题主要还是使用递归解决。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels