相同的树

来源Leetcode第100题相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

递归

最简单的比较根节点然后递归比较左子树和右子树，没有什么好说的。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public boolean isSameTree(TreeNode p, TreeNode q) {
    // 如果两个根节点都为空，那肯定是相等的
    if (p == null && q == null) return true;
    // 有一个不为空，那就不等了
    if (q == null || p == null) return false;
	// 都不为空，比较值
	//然后开始递归比较左右子树
    if (p.val != q.val) return false;
    return isSameTree(p.right, q.right) &&
            isSameTree(p.left, q.left);
  }
}

双向队列

本来后面是想用两个栈写的，但是笔记本电池续航尿崩了，先看看题解里是怎么写的吧。

题解采用了双向队列，并不是栈，emm

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Deque<TreeNode> stack1 = new LinkedList<>();
        Deque<TreeNode> stack2 = new LinkedList<>();
		
		//根节点入栈(队列)
        stack1.push(p);
        stack2.push(q);
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
		
		    //栈顶元素出栈
            TreeNode a = stack1.pop();
            TreeNode b = stack2.pop();
			//比较出栈元素
            if (a == null && b == null) continue;
            if (a != null && b != null && a.val == b.val) {
			//值相等或者都为空将左右子树入栈
                stack1.push(a.left);
                stack1.push(a.right);
                stack2.push(b.left);
                stack2.push(b.right);
            } else return false;
        }
        return stack1.isEmpty() && stack2.isEmpty();
    }
}