每天一道leetcode-101對稱二叉樹

• 2019 年 10 月 4 日
• 筆記

辣條走起，每月的leetcode刷題99元獎勵就靠大家啦~

前言

今天的題目 每天的題目見github(看最新的日期): https://github.com/gzc426 具體的題目可以去牛客網對應專題去找。

昨天的題解

題目

每天一道leetcode-101對稱二叉樹 分類：二叉樹

題目詳述

給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。 1 / 2 2 / / 3 4 4 3 但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的: 1 / 2 2 3 3 說明:

如果你可以運用遞歸和迭代兩種方法解決這個問題，會很加分。

題目詳解

思路

• 1. 樹是空的，true。
• 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 isSymmetric(TreeNode root) {          if (root == null) {              return true; //根節點是空，返回true          }else {              return isSymmetric(root.left, root.right);//然後進行遞歸，思路的實現          }      }      private boolean isSymmetric(TreeNode left, TreeNode right) {          if (left == null && right == null) {//左右子樹都是空，肯定對稱，true              return true;          }else if (left == null || right == null) {              return false;//左右子樹只有一個為空，那麼返回false          }          if(left.val != right.val)//左右子樹都不為空，但是值不相等，返回false              return false;          //這裡是左右子樹的值相等，然後遞歸判斷每個子樹          return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);      }  }

程式碼截圖（避免亂碼）