Compare Leaf Traversal

• Time : O(n + m)
• Space : O(leaf(n) + leaf(m))

c++

using namespace std;

// This is an input class. Do not edit.

class BinaryTree {
public:
    int value;
    BinaryTree *left = nullptr;
    BinaryTree *right = nullptr;

    BinaryTree(int value) { this->value = value; }
};

void travel(vector<int>& res, BinaryTree* tree) {
    if(tree->left == nullptr and tree->right == nullptr) res.push_back(tree->value);
    else {
        if(tree->left) travel(res, tree->left);
        if(tree->right) travel(res, tree->right);
    }
}

bool compareLeafTraversal(BinaryTree *tree1, BinaryTree *tree2) {
    if(tree1 == nullptr) return tree2 == nullptr;
    if(tree2 == nullptr) return tree1 == nullptr;
    vector<int> leaf1, leaf2;
    travel(leaf1, tree1);
    travel(leaf2, tree2);
    return leaf1 == leaf2;
}

• Time : O(n + m)
• Space : O(leaf(n))

c++

using namespace std;

// This is an input class. Do not edit.
class BinaryTree {
public:
    int value;
    BinaryTree *left = nullptr;
    BinaryTree *right = nullptr;

    BinaryTree(int value) { this->value = value; }
};

void travel1(vector<int>& res, BinaryTree* tree) {
    if(tree->left == nullptr and tree->right == nullptr) res.push_back(tree->value);
    else {
        if(tree->left) travel1(res, tree->left);
        if(tree->right) travel1(res, tree->right);
    }
}

bool travel2(vector<int>& res, BinaryTree* tree) {
    if(tree->left == nullptr and tree->right == nullptr) {
        if(res.empty() or tree->value != res.back()) return false;
        res.pop_back();
        return true;
    } else {
        if(tree->right) {
            if(!travel2(res, tree->right)) return false;
        }
				if(tree->left) {
            if(!travel2(res, tree->left)) return false;
        }
        return true;
    }
}

bool compareLeafTraversal(BinaryTree *tree1, BinaryTree *tree2) {
    if(tree1 == nullptr) return tree2 == nullptr;
    if(tree2 == nullptr) return tree1 == nullptr;
    vector<int> leaf;
    travel1(leaf, tree1);
    return travel2(leaf, tree2);
}