100. Same Tree

Problem from leetcode 100. Same Tree

---

主要有两种写代码的方式

1. 递归 recursive time complexity: O(n) | space complexity: O(1)
2. 迭代 iterative time complexity: O(n) | space complexity: O(1)

---

1, 递归 recursive

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL) return true;
        if(p == NULL || q == NULL) return false;
        return p->val==q->val && isSameTree(p->left, q->left)&& isSameTree(p->right, q->right);
    }
};

---

2, 迭代 iterative

迭代的话需要queue做辅助:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> tool;
        tool.push(p); tool.push(q);
        while(!tool.empty())
        {
            TreeNode *first = tool.front(); tool.pop();
            TreeNode *second = tool.front(); tool.pop();
            if(first == NULL && second == NULL) continue;
            if(first == NULL || second == NULL) return false;
            if(first->val != second->val) return false;
            tool.push(first->left);
            tool.push(second->left);
            tool.push(first->right);
            tool.push(second->right);
        }
        return true;
    }
};

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null) return true;
        if(p==null || q==null) return false;
        return p.val==q.val && isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);
    }
}

Python:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p is None and q is None: return True
        if p is None or q is None: return False
        return p.val==q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)