Non-recursive and no memory alloc method with C


  • 0
    E
    bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q || p->val != q->val) return false;
    p->val = NULL;
    q->val = NULL;
    while(p && q)
    {
    	if (p->left && (!q->left || p->left->val != q->left->val)) return false;
    	if (p->right && (!q->right || p->right->val != q->right->val)) return false;
    	if (q->left && (!p->left || q->left->val != p->left->val)) return false;
    	if (q->right && (!p->right || q->right->val != p->right->val)) return false;
    	if (p->right)
    	{
    		p->right->val = p->val;
    		q->right->val = q->val;
    	}
    	if (p->left)
    	{
    		if (p->right)
    		{
    			p->left->val = (int)p->right;
    			q->left->val = (int)q->right;
    		}
    		else
    		{
    			p->left->val = p->val;
    			q->left->val = q->val;
    		}
    	}
    
    	if (p->left)
    	{
    		p = p->left;
    		q = q->left;
    	}
    	else if (p->right)
    	{
    		p = p->right;
    		q = q->right;
    	}
    	else
    	{
    		p = (struct TreeNode*)p->val;
    		q = (struct TreeNode*)q->val;
    	}
    }
    return true;
    

    }

    this method makes binary-tree comparison to linked-list comparison,without stack or heap alloc.


Log in to reply
 

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