LeetCode Identical Binary Tree 相同二叉树-蒲公英云

LeetCode Identical Binary Tree 相同二叉树

题目描述：

Check if two binary trees are identical. Identical means the two binary trees have the same structure and every identical position has the same value.

样例输入：

1             1
   / \           / \   2   2   and   2   2
 /             /
4             4
1             1
   / \           / \   2   3   and   2   3
 /               \ 4                 4

样例输出：

true
false

解法一：

有树的地方就有递归

private boolean isIdenticalRecursion(TreeNode a, TreeNode b) {
   if (a == null && b == null) {
        return true;
    }
    if ((a == null && b != null) || (a != null && b == null) || (a.val != b.val)) {
        return false;
    }
    return isIdenticalRecursion(a.left, b.left) && isIdenticalRecursion(a.right, b.right);
}

解法二：

递归能实现的循环也能实现

private boolean isIdenticalPreOrder(TreeNode a, TreeNode b) {
     Stack<TreeNode> stack1 = new Stack<>();
     Stack<TreeNode> stack2 = new Stack<>();
     stack1.push(a);
     stack2.push(b);
     while (!stack1.empty() && !stack2.empty()) {
         TreeNode tmp1 = stack1.pop();
         TreeNode tmp2 = stack2.pop();
         if (tmp1.val!=tmp2.val){
             return false;
         }
         if (tmp1.right!=null){
             stack1.push(tmp1.right);
         }
         if (tmp2.right!=null){
             stack2.push(tmp2.right);
         }
         if (stack1.size()!=stack2.size()){
             return false;
         }
         if (tmp1.left!=null){
             stack1.push(tmp1.left);
         }
         if (tmp2.left!=null){
             stack2.push(tmp2.left);
         }
         if (stack1.size()!=stack2.size()){
             return false;
         }
     }
     return stack1.size() == stack2.size();
 }