相同的树

相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入:       1         1

          / \       / \

         2   3     2   3

 

        [1,2,3],   [1,2,3]

输出: true

示例 2:

输入:      1          1

          /           \

         2             2

       [1,2],     [1,null,2]

输出: false

示例 3:

输入:       1         1

          / \       / \

         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

循环：不断重复进行某一运算、操作。

迭代：不断对前一旧值运算得到新值直到达到精度。一般用于得到近似目标值，反复循环同一运算式（函数），并且总是把前一 次运算结果反代会运算式进行下一次运算

递推：从初值出发反复进行某一运算得到所需结果。-----从已知到未知，从小到达（比如每年长高9cm，20年180，30后270）

回溯：递归时经历的一个过程。

递归：从所需结果出发不断回溯前一运算直到回到初值再递推得到所需结果----从未知到已知，从大到小，再从小到大。递归(Recursion)是从归纳法(Induction)衍生出来的。

递归法：一个运算（操作），可以通过不断调用本身的运算形式，往往需要通过前一次的结果来得到当前运算的结果，因而，程序运行时，总是先一次次地「回溯」前一次的结果（回溯过程中这些结果是未知的，直到回溯到初值令回溯终止，再层层递推回来得到当前要求的值）

回溯法：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。等同于树的后续遍历或图的深度优先搜索。因此，回溯法一般结合递归来实现。

注意：回溯法求解问题时，实际时遍历树或图的过程。

方法1        递归

一个完整的递归应该有下面三个条件，否则就是不合格的递归

  1. 明确递归的终止方法（一个递归必须有他递推到头的界定，否则将会是无限递归 ）
  2. 明确的终止时处理方法
  3. 重复调用自身并缩小问题规模 

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


class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && p == null) {
        	return true;
        }
		if (p == null || q == null) {
          return false;
        }

        if (p.val != q.val) {
        	return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if (p != null && q != null && p.val == q.val){
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
        return false;
    }
}


方法2 队列

public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(p);
        queue.add(q);//两个树的节点进队列
        while(!queue.isEmpty()){
            TreeNode f=queue.poll();//出队列，如果队列头为空，返回null
            TreeNode s=queue.poll();
            if(f==null&&s==null) continue;
            else if(f == null || s == null || f.val != s.val) return false;
            queue.add(f.left);
            queue.add(s.left);
            queue.add(f.right);
            queue.add(s.right);
        }
        return true;
    }