LeetCode - Easy - 100. Same Tree-蒲公英云

LeetCode - Easy - 100. Same Tree

Topic

Tree, Depth-first Search

Description

https://leetcode.com/problems/same-tree/

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
Output: true

Example 2:

Input:     1         1
          /           \
         2             2
        [1,2],     [1,null,2]
Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
Output: false

Analysis

方法一：递归前序遍历

方法二：非递归前序遍历

Submission

import java.util.Arrays;
import java.util.LinkedList;
import com.lun.util.BinaryTree.TreeNode;
public class SameTree { 
    //方法一：递归前序遍历
    public boolean isSameTree1(TreeNode p, TreeNode q) { 
        if (p == null && q != null || p != null && q == null)
            return false;
        if (p != null && q != null) { 
            if (p.val != q.val) { 
                return false;
            }
            // 判断左右子树
            return isSameTree1(p.left, q.left) && isSameTree1(p.right, q.right);
        }
        return true;
    }
    //方法二：非递归前序遍历
    public boolean isSameTree2(TreeNode root1, TreeNode root2) { 
        TreeNode p = root1, q = root2;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while(true) { 
            if(p == null && q != null || p != null && q == null) { 
                return false;
            }
            if(p != null && q != null) { 
                if(p.val != q.val) { 
                    return false;
                }
                //下列push的精简
                stack.addAll(0, Arrays.asList(p.left, q.left, p.right, q.right));
// stack.push(q.right);
// stack.push(p.right);
// 
// stack.push(q.left);
// stack.push(p.left);
            }
            if(stack.isEmpty()) { 
                break;
            }else { 
                p = stack.pop();
                q = stack.pop();
            }
        }
        return true;
    }
}

Test

import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.util.BinaryTree.TreeNode;
public class SameTreeTest { 
    @Test
    public void test() { 
        SameTree obj = new SameTree();
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);
        assertTrue(obj.isSameTree1(root1, root2));
        assertTrue(obj.isSameTree2(root1, root2));
    }
    @Test
    public void test2() { 
        SameTree obj = new SameTree();
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        TreeNode root2 = new TreeNode(1);
        root2.right = new TreeNode(2);
        assertFalse(obj.isSameTree1(root1, root2));
        assertFalse(obj.isSameTree2(root1, root2));
    }
    @Test
    public void test3() { 
        SameTree obj = new SameTree();
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(1);
        TreeNode root2 = new TreeNode(1);
        root2.right = new TreeNode(1);
        root2.right = new TreeNode(2);
        assertFalse(obj.isSameTree1(root1, root2));
        assertFalse(obj.isSameTree2(root1, root2));
    }
}