Subtree query (suboptimal)


  • 0
    D

    Subtree query algorithm. Not the fastest or cleanest solution, but it works.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    struct TreeTraversalNode{
        TreeNode* node;
        int subtree_size_left;
        int subtree_size_right;
        int subtree_size;
        int node_value;
        bool is_duplicate;
        //TreeTraversalNode();
    };
    
    class Solution {
    public:
        void traverseTree(TreeNode* node, vector<TreeTraversalNode>& traversal_nodes) {
            if (!node)
                return;
            
            TreeTraversalNode traversal_node;
            traversal_node.node = node;
            traversal_node.subtree_size = 1;
            traversal_node.subtree_size_left = 0;
            traversal_node.subtree_size_right = 0;
            traversal_node.node_value = node->val;
            traversal_node.is_duplicate = false;
            
            int node_id = traversal_nodes.size();
            
            traversal_nodes.push_back(traversal_node);
            
            if (node->left) {
                traverseTree(node->left, traversal_nodes);
                traversal_nodes[node_id].subtree_size_left = traversal_nodes[node_id + 1].subtree_size;
                traversal_nodes[node_id].subtree_size += traversal_nodes[node_id].subtree_size_left;
            }
            
            int node_id_right = traversal_nodes.size();
            
            if (node->right) {
                traverseTree(node->right, traversal_nodes);
                traversal_nodes[node_id].subtree_size_right = traversal_nodes[node_id_right].subtree_size;
                traversal_nodes[node_id].subtree_size += traversal_nodes[node_id].subtree_size_right;
            }
        }
        
        vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
            vector<TreeNode*> duplicate_nodes;
            vector<TreeTraversalNode> traversal_nodes;
            
            traverseTree(root, traversal_nodes);
            
            for (int i = 0; i < traversal_nodes.size(); i++) {
                if (traversal_nodes[i].is_duplicate)
                    continue;
                
                bool first_duplicate_found = false;
                for (int j = i + 1; j < traversal_nodes.size(); j++) {
                    if (traversal_nodes[i].subtree_size_left == traversal_nodes[j].subtree_size_left &&
                        traversal_nodes[i].subtree_size_right == traversal_nodes[j].subtree_size_right) {
                        bool is_duplicate = true;
                        for (int k = 0; k < traversal_nodes[i].subtree_size; k++) {
                            if (traversal_nodes[i + k].node_value != traversal_nodes[j + k].node_value ||
                                (traversal_nodes[i + k].subtree_size_left != traversal_nodes[j + k].subtree_size_left &&
                                 traversal_nodes[i + k].subtree_size_right != traversal_nodes[j + k].subtree_size_right)) {
                                is_duplicate = false;
                                break;
                            }
                        }
                        if (is_duplicate) {
                            traversal_nodes[i].is_duplicate = true;
                            traversal_nodes[j].is_duplicate = true;
                            if (!first_duplicate_found) {
                                duplicate_nodes.push_back(traversal_nodes[i].node);
                                first_duplicate_found = true;
                            }
                        }
                    }
                }
            }
            
            return duplicate_nodes;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.