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