100. 相同的树

题意：

解题思路：

思路：[递归+迭代]
1. 递归判断 p 和 q 是不是 null，如果不是则判断它们的值是否相等，继续递归子节点；
2. 先入栈根节点，每次迭代将当前结点弹出，然后进行判断；
    * p 和 q 非空
    * p->val 等于q->val
3. 满足上面条件，则继续压入两树的左右子结点；

PHP代码实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $p
     * @param TreeNode $q
     * @return Boolean
     */
    function isSameTree($p, $q) {
        if ($p == null && $q == null) return true;
        if ($p == null || $q == null) return false;
        return $p->val == $q->val 
            && $this->isSameTree($p->left, $q->left) && $this->isSameTree($p->right, $q->right);
    }
    function isSameTreeIterative($p, $q) {
        $s = new SplStack;
        $s->push($p);
        $s->push($q);
        while (!$s->isEmpty()) {
            $s1 = $s->pop();
            $s2 = $s->pop();
            if ($s1 == null && $s2 == null) continue;
            if ($s1 == null || $s2 == null) return false;
            if ($s1->val != $s2->val) return false;
            $s->push($s1->left);
            $s->push($s2->left);
            $s->push($s1->right);
            $s->push($s2->right);
        }
        return true;
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    } 
    if p == nil || q == nil {
        return false
    }
    if p.Val != q.Val {
        return false
    }
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}