【Daily Interview】- 14 相同的树

题目

!! 题目来源：相同的树 - 力扣

分析

所谓树，其实是基于链表之上的一种数据结构，通过之前的学习，我们已经清楚了什么是链表，而在此之上，若节点不仅仅有一个 next，而是有多个 next 指向不同的节点，那便形成了树，可见下图：

其中顶部的节点被称为树的根节点，根据上图，我们可以大致得出树的结构：

class TreeNode {
    constructor(value) {
        this.val = value
        this.children = []
    }
}

在树的基础上，如果规定任意节点至多有两个节点，分别称为 left 和 right，那么这棵树便是一棵二叉树，具体可见下图：

基本知识的铺垫暂时到这，随着后面的刷问题会继续深入，接下来我们分析一下题目：

• 这是一颗二叉树
• 树在结构上相同，并且节点具有相同的值，则判定它们相同

根据上述两点，我们可以得出以下的一些信息：

• 树的结构大致如下：

function TreeNode(val, left, right) {     
   this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

• 树需要结构和每个节点的值相同才能判定相同，比如下面两树就是不同的：

结合上述信息，我们应当在代码层面判断两树相等呢？

• 首先我们一定是需要用递归的手段来遍历树
• 其次，当我们递归的时候，实现应该聚焦在当前节点，收窄关注点
• 对于当前节点，有什么可以判断的呢？

  • 如果当前节点皆为空，显然它们是相等的
  • 如果一个节点为空，一个不为空，显然让门不相等
  • 如果二者皆不为空，但二者值不相等，那它们必不相等

大体思路如上，这里按部就班实现代码即可：

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);
};

结果如下：

!! ? tip：或许有的读者会觉得上述条件忽略了二者皆不为空，但二者值相等的情况，认为这个时候二者应该相等才对，但无论从代码还是思路中都没有体现这点。但实际上，这样的思考存在一个盲区，那就是子节点的相等问题，虽然在递归的时候要将目光聚焦到当前节点，但是不能忘记全局的判断。