转载

【LeetCode OJ】Same Tree

题目：Given two binary trees, write a function to check if they are equal or not.

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

解题思路：这题的基本意思就是要判断两个二叉树是否相同，因为递归思想不是很熟练，所以一开始用非递归的方法写的，但是老有一个case过不了。后来硬着头皮用递归的思路想了一下，总算是通过了所有的测试用例。以前每次遇到递归的问题都会有点抗拒，担心会出点bug，平时也练习的很少，下面还是简单总结一下递归的思想:

程序自身调用自身的编程技巧称为递归，递归有四个特性：

1.必须有可最终达到的终止条件，否则程序将陷入无穷循环；

2.子问题在规模上比原问题小，或更接近终止条件；

3.子问题可通过再次递归调用求解或因满足终止条件而直接求解；

4.子问题的解应能组合为整个问题的解。

上面的这道题就是典型的递归问题，首先判断两个二叉树根节点是否相同，再判断其左右孩子节点是否相同。代码如下：

/*  判断两个二叉树是否相同  */ class TreeNode {  int val;  TreeNode left;  TreeNode right;  TreeNode(int x) { val = x; }  } public class Solution {  public boolean isSameNode(TreeNode a,TreeNode b) //判断两个节点是否相同  {   if(a==null&&b==null)  //均为空节点，相同    return true;   else if(a!=null&&b!=null&&a.val==b.val)//均不为空节点且节点值相等，相同    return true;   else //其余情况均为不相同    return false;  }  public boolean isSameTree(TreeNode p, TreeNode q)   {   if(p==null&&q==null)    return true;   if(!isSameNode(p, q))      return false;   if(isSameNode(p, q))    return isSameTree(p.left, q.left)&&isSameTree(p.right, q.right);   return false;  } }