101. 对称二叉树

思路

可以按照内侧和外侧，一直比较树的两个左右节点。
递归就是一直循环判断到最后一层，此时子节点都为null了就输出true，过程中有任何不对称的样式就输出false退出递归。

要点

就是要分析清楚各种情况，

• 左右子节点都为null✔
• 其中一个为null另一个不为null✖

• 值不相等✖

  方案

  递归、队列、栈都能做。
  队列、栈就是让内侧、外侧的两两节点成对进出来判断。

  递归

  ```cpp var isSymmetric = function(root) { const compare =function(left,right){

    if(!left&&!right)return true;
    else if(left===null||right===null||left.val!==right.val) return false;
    let outside =compare(left.left,right.right);
    let inside =compare(left.right,right.left);
    return outside&&inside;

  } if(!root) return true;

  return compare(root.left,root.right);

};

<a name="paaoj"></a>
### 队列
```cpp
var isSymmetric = function(root) {
  //迭代方法判断是否是对称二叉树
  //首先判断root是否为空
  if(root===null){
      return true;
  }
  let queue=[];
  queue.push(root.left);
  queue.push(root.right);
  while(queue.length){
      let leftNode=queue.shift();//左节点
      let rightNode=queue.shift();//右节点
      if(leftNode===null&&rightNode===null){
          continue;
      }
      if(leftNode===null||rightNode===null||leftNode.val!==rightNode.val){
          return false;
      }
      queue.push(leftNode.left);//左节点左孩子入队
      queue.push(rightNode.right);//右节点右孩子入队
      queue.push(leftNode.right);//左节点右孩子入队
      queue.push(rightNode.left);//右节点左孩子入队
  }
  return true;
};

100. 相同的树

类似题目，但比较的是两棵树。
从根开始比较即可。
思路一致。

var isSameTree = function(p, q) {
    const compare =function(root1,root2){
        if(!root1&&!root2)return true;
        else if(root1===null||root2===null||root1.val!==root2.val)return false;

        let leftcompare =compare(root1.left,root2.left);
        let rightcompare =compare(root1.right,root2.right);

        return leftcompare&&rightcompare;
    }

    return compare(p,q);
};

//更精简写法
var isSameTree = function(p, q) {
    if (p === null && q === null) {
        return true;
    } else if (p === null || q === null) {
        return false;
    } else if (p.val !== q.val) {
        return false;
    } else {
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
};

572. 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
一个树是另一个树的子树 则

• 要么这两个树相等
• 要么这个树是左树的子树
• 要么这个树是右树的子树

方法1

递归查找，深度优先搜索暴力匹配。
从 根节点开始，判断两个树是否相同（结合100题），不同则继续从根节点的左右子树开始查找。

方法二：深度优先搜索序列上做串匹配

这个方法需要我们先了解一个「小套路」：一棵子树上的点在深度优先搜索序列（即先序遍历）中是连续的。了解了这个「小套路」之后，我们可以确定解决这个问题的方向就是：
把 ss 和 tt 先转换成深度优先搜索序列，然后看 tt 的深度优先搜索序列是否是 ss 的深度优先搜索序列的「子串」。但这是一个必要不充分条件。
假设 ss 由两个点组成，11 是根，22 是 11 的左孩子；tt 也由两个点组成，11 是根，22 是 11 的右孩子。这样一来 ss 和 tt 的深度优先搜索序列相同，可是 tt 并不是 ss 的某一棵子树。
为了解决这个问题，我们可以引入两个空值 lNull 和 rNull，当一个节点的左孩子或者右孩子为空的时候，就插入这两个空值，这样深度优先搜索序列就唯一对应一棵树。处理完之后，就可以通过判断「ss 的深度优先搜索序列包含 tt 的深度优先搜索序列」来判断答案。

方法三：树哈希