Leetcode 114. 二叉树展开为链表_二叉树展开为链表 python leetcode

先整成左子树的形式【右子结点在先序遍历中递归返回后还要遍历，不能覆盖】

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