99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区

1. 題目

100. 相同的樹^[1]

2. 描述

給定兩個二叉樹，編寫一個函數(shù)來檢驗它們是否相同。

如果兩個樹在結(jié)構(gòu)上相同，并且節(jié)點具有相同的值，則認(rèn)為它們是相同的。

示例 1:

   

示例 2:

   

示例 3:

   

3. 思路

利用二叉樹刷題遞歸遍歷框架，先對根節(jié)點進(jìn)行操作，然后再遞歸左右子節(jié)點即可。

1. 當(dāng)兩棵樹的當(dāng)前節(jié)點都為 null 時返回 true

2. 當(dāng)其中一個為 null 另一個不為 null 時返回 false

3. 當(dāng)兩個都不為空但是值不相等時，返回 false

4. 以上三步完成對根節(jié)點的操作，接下來對左右子節(jié)點進(jìn)行遞歸即可

// 遞歸訪問
void traverse(TreeNode root){
   // 前序遍歷，先操作根節(jié)點
   traverse(root.left);
   // 中序遍歷，操作左子節(jié)點
   traverse(root.right);
   // 后序遍歷，操作右子節(jié)點
}

4. 實現(xiàn)

public boolean isSameTree(TreeNodeTest p, TreeNodeTest q) {
   /*
    * 先進(jìn)行根節(jié)點的判斷
    */

   // 兩者均為 null，說明相等
   if (p == null && q == null) {
       return true;
   }

   // 其中一個為 null，說明不相等
   if (p == null || q == null) {
       return false;
   }

   // 兩者均非 null，但值不同，說明不相等
   if (p.val != q.val) {
       return false;
   }

   // 根節(jié)點判斷之后，在判斷左右節(jié)點
   return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}