【Leetcode】114. Flatten Binary Tree to Linked List

短命女 2022-02-16 12:25 164阅读 0赞

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

For example, given the following tree:

1
       / \
      2   5
     / \   \
    3   4   6

The flattened tree should look like:

1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6

题目大意：

按照先根节点，左节点，右节点的顺序排列出一个仅包含右节点的树。

解题思路：

vector先保存父节点，再左节点，右节点保存的顺序遍历。

/**
     * 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 {
    private:
        vector<int> nums;
        void helper(TreeNode *root){
            if(root->left==NULL&&root->right==NULL){
                nums.push_back(root->val);
                return ;
            }
            nums.push_back(root->val);
            if(root->left) helper(root->left);
            
            if(root->right) helper(root->right);
        }
    public:
        void flatten(TreeNode* root) {
            if(root){
                helper(root);
            // sort(nums.begin(), nums.end());
            root->val = nums[0];
            TreeNode* tmp=root;
            // root = tmp;
            for(int i=1;i<nums.size();i++){
                if(tmp->left){
                    tmp->left=nullptr;
                }
                if(tmp->right==NULL){
                    TreeNode *t = new TreeNode(nums[i]);
                    tmp->right = t;
                    tmp = tmp->right;
                }else{
                    tmp->right->val = nums[i];
                    tmp = tmp->right;
                }
            }
            }
            
        }
    };