Recursion in C++

  • 1

    My solution uses recursion. The main idea is as follows: I have a simple base case that return true if both TreeNode are null. Another base case is that If one is null and the other is not null than return false.

    My set of rules will be comparing the values of the two TreeNodes and comparing their sub-trees.

    class Solution {
        bool isSameTree(TreeNode *p, TreeNode *q) {
    		if (p == NULL && q == NULL) {
    			return true;
    		else if (p != NULL && q != NULL) {
    			return ((p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
    			return false;

  • 0

    What's the time complexity of this?

  • 0

    If we only count the item to item comparison, this solution should be O(n).

Log in to reply

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