相同的树

DFS和BFS

1. DFS -> 深度优先遍历
2. BFS -> 广度优先遍历

DFS如图

BFS如图

3. 区别

   对于算法来说 无非就是时间换空间 空间换时间

   1. 深度优先不需要记住所有的节点, 所以占用空间小, 而广度优先需要先记录所有的节点占用空间大
   2. 深度优先有回溯的操作(没有路走了需要回头)所以相对而言时间会长一点
   3. 深度优先采用的是堆栈的形式, 即先进后出
   4. 广度优先则采用的是队列的形式, 即先进先出

题目

输入:       1         1
          / \       / \
         2   3     2   3

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

输出: true

示例

输入:       1         1
          / \       / \
         2   3     2   3

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

输出: true


输入:      1          1
          /           \
         2             2

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

输出: false


输入:       1         1
          / \       / \
         2   1     1   2

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

输出: false

解法

DFS解法

其实就是递归各个节点。根据题目分析得出一下几点。

1. 当两棵树的当前节点都为 null 时返回 true
2. 当其中一个为 null 另一个不为 null 时返回 false
3. 当两个都不为空但是值不相等时，返回 false

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
   if(p == null && q == 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)

};

BFS解法

利用数组队列，把待对比的节点放入队列，每次取出队列第一个校验。当队列为空时，说明两个节点完全一样。 这时return true，反之在循环中写入判断条件，需要注意的是与DFS相比，当两个节点都同时为null时，是跳出循环 进行下一次循环，不是直接return true。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    let cace=[
        {p,q}
    ]
    while(cace.length){
        let seq=cace.shift()
        if(seq.p == null && seq.q == null) continue
        if(seq.p == null || seq.q == null) return false
        if(seq.p.val != seq.q.val) return false
        cace.push(
            {
                p:seq.p.left,
                q:seq.q.left
            },
            {
                p:seq.p.right,
                q:seq.q.right
            }
        )
    }
    return true
};