Cinte's Leetcode Record
0%

114. Flatten Binary Tree to Linked List

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

114. Flatten Binary Tree to Linked List

我越来越菜了
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
30
31
32
33
34
35
36
37
38
39
40
/**
 * 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) {}
 * };
 */
 // preorder traversal 是 root -> left -> right
 // 此方法是将左子树插入到root 和 右子树中间。
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* now = root; // 当前节点
        while(now)
        {
            // 如果当前节点存在左子树，则需要优先遍历
            if(now->left) 
            {
                TreeNode* pre = now->left;
                // 将pre指针移到左子树的右子树的最右端
                while(pre->right)
                {
                    pre = pre->right;
                }
                // 使右子树最末端的右边只想原节点的右子树
                pre->right = now->right;
                // 将源节点的右边指向左边
                now->right = now->left;
                // 上述的操作之后，root的右子树是原来的左子树
                now->left = nullptr;
            }
            // 走到下一个节点，顺序始终是先左后右
            now = now->right;
        }
    }
};

太强了

review

和上面区别就是他留了一部分左子树给后面处理，而我就直接处理完了

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
30
31
32
33
34
35
36
37
/**
 * 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* pt = root;
        while(pt)
        {
            if(pt->left)
            {
                auto cur = pt->left;
                TreeNode* pre;
                while(cur)
                {
                    pre = cur;
                    if(cur->right)
                        cur = cur->right;
                    else
                        cur = cur->left;
                }
                pre->right = pt->right;
                pt->right = pt->left;
                pt->left = nullptr;
            }
            pt = pt->right;
        }
    }
};