Preorder traversal using string and hashmap


  • 0
    J
    class Solution {
    public:
        string preorder(TreeNode* root, unordered_map<string, int>& freq, vector<TreeNode*>& res) {
            if(root != NULL) {
                string left = preorder(root -> left, freq, res);
                string right = preorder(root -> right, freq, res);
                
                string str = to_string(root -> val) + " " + left + right;
                
                if(freq[str] == 1) res.push_back(root);
                freq[str]++;
                return str;
            } else {
                return "null ";
            }
        }
        vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
            unordered_map<string, int> freq;
            vector<TreeNode*> res;
            preorder(root, freq, res);
            return res;
        }
    };
    

  • 0
    C

    This is postorder traversal


  • 0
    J

    @Raktima Hi, I believe it is preorder because of the key which is:

    string str = to_string(root -> val) + " " + left + right;
    

    It follows the format of visit(current), visit(current -> left), visit(current -> right). If you try a few trees and print the variable "str", you can see this


  • 0
    L

    @jamarshon No. This is a postorder. left and right are got from recursion.


  • 0
    J

    @lavender_sz sorry i meant that the key for the hashmap is the preorder sequence of the subtrees. the sequence which these nodes are visited by the function is postorder as you mentioned


Log in to reply
 

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