[LeetCode]114. Flatten Binary Tree to Linked List

Problem

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

1
2
3
4
5
    1
/ \
2 5
/ \ \
3 4 6

The flattened tree should look like:

1
2
3
4
5
6
7
8
9
10
11
1
\
2
\
3
\
4
\
5
\
6

Solution

二叉树的先序遍历。这里的难点在于对二叉树进行直接修改,没有返回,直接修改原二叉树。

本来想法是利用二叉树先序遍历的递归形式,同时传入一个指针变量,记录当前节点的前序遍历的前一个节点,遍历时完成指针的赋值,最后再对指针和根节点指针进行交换,结果出错。

最后,换成二叉树先序遍历的非递归形式,直接对每个界定的指针进行变更。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
// 先序遍历:非递归形式
// 难点在于:对直接修改,不用返回值
TreeNode* prev = new TreeNode(-1);
stack<TreeNode*> ss;
if (root) ss.push(root);

while (!ss.empty()){
TreeNode* temp = ss.top();
ss.pop();
if (temp->right) ss.push(temp->right);
if (temp->left) ss.push(temp->left);
temp->left = nullptr;
prev->right = temp;
prev = temp;
}
}
};
您的支持就是我更新的最大动力!谢谢!