题目

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:

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

Example 2:

  1. Input:     1         1
  2.           /           \
  3.          2             2
  5.         [1,2],     [1,null,2]
  7. Output: false

Example 3:

  1. Input:     1         1
  2.           / \       / \
  3.          2   1     1   2
  5.         [1,2,1],   [1,1,2]
  7. Output: false

题意

判断两个二叉树是否完全一样。

思路

递归比较每一个结点是否相同。

代码实现

Java

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public boolean isSameTree(TreeNode p, TreeNode q) {
  12.         if (p == null && q == null) {
  13.             return true;
  14.         } else if (p == null || q == null || p.val != q.val) {
  15.             return false;
  16.         } else {
  17.             return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  18.         }
  19.     }
  20. }

JavaScript

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} p
  11.  * @param {TreeNode} q
  12.  * @return {boolean}
  13.  */
  14. var isSameTree = function (p, q) {
  15.   if (!p && !q) {
  16.     return true
  17.   } else if (!p || !q || p.val !== q.val) {
  18.     return false
  19.   }
  21.   return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
  22. }