Find Elements in a Contaminated Binary Tree（C++在受污染的二叉树中查找元素）

谁借莪１个温暖的怀抱￠ 2023-01-01 05:46 66阅读 0赞

解题思路：

（1）前序遍历

/**
     * 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 FindElements {
        TreeNode *head=NULL;
        bool tag = false;
    public:
        
        TreeNode* cover(TreeNode* root) {
            if(root) {
                root->val=root->val==-1?0:root->val;
                if(root->left) root->left->val=2*root->val+1; 
                if(root->right) root->right->val=2*root->val+2; 
                root->left = cover(root->left);
                root->right = cover(root->right);
                return root;
            } else return NULL;
        }
        
        void find_target(TreeNode *root,int target) {
            if(root) {
                if(root->val==target) {
                    tag=true;
                    return;
                }
                find_target(root->left,target);
                find_target(root->right,target);
            }
        }
        
        FindElements(TreeNode* root) {
            head = cover(root);
        }
        
        bool find(int target) {
            find_target(head,target);
            if(tag) {
                tag=false;
                return true;
            }
            else {
                tag=false;
                return false;
            }
        }
    };
    
    /**
     * Your FindElements object will be instantiated and called as such:
     * FindElements* obj = new FindElements(root);
     * bool param_1 = obj->find(target);
     */