[leetcode] 100.Same Tree

100. Same Tree

Given the roots of two binary trees p and q, 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: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

The number of nodes in both trees is in the range [0, 100].
-104 <= Node.val <= 104

recursion

  Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
 	    TreeNode(int val) { this.val = val; }
       	TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) return p == null && q == null;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }

1. p, q 둘 중에 하나라도 null 일 때, 둘 다 null 이면 true, 하나라도 null이 아니면 false
   1. 둘 다 null 이면 노드가 아예 존재하지 않는 경우이니까 true
   2. 하나는 null 인데, 다른 하나가 null 이 아니라면 당연히 일치하지 않으니까 false 반환
2. null 값이 없는 경우, 해당 노드의 다음 왼쪽 노드, 해당 노드의 다음 오른쪽 노드가 모드 동일한 경우에만 true

---

DFS

	class Solution {
		public boolean isSameTree(TreeNode p, TreeNode q) {

			if (p == null && q == null)
				return true;

			if (p == null || q == null)
				return false;

			Stack<TreeNode> stack1 = new Stack();
			Stack<TreeNode> stack2 = new Stack();

			stack1.push(p);
			stack2.push(q);

			while (!stack1.isEmpty() && !stack2.isEmpty()) {
				TreeNode node1 = stack1.pop();
				TreeNode node2 = stack2.pop();

				if (node1.val != node2.val) {
					return false;
				}

				if (node1.left != null && node2.left != null) {
					stack1.push(node1.left);
					stack2.push(node2.left);
				} else if (!(node1.left == null && node2.left == null))
					return false;

				if (node1.right != null && node2.right != null) {
					stack1.push(node1.right);
					stack2.push(node2.right);
				} else if (!(node1.right == null && node2.right == null))
					return false;

			}

			if (stack1.size() != stack1.size())
				return false;
			return true;
		}
	}