我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

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

進階：

• 你可以運用遞歸和迭代兩種方法解決這個問題嗎？

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/symmetric-tree
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

思路1-鏡像遞歸校驗值

步驟：

1. 先驗根節點，然後從左右節點開始鏡像遞歸；
2. 也可以從根開始，但其實進行了兩次校驗（鏡像的），沒有必要，因為根必然鏡像；

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $

演算法源碼示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年1月10日 下午10:39:22 
 * @Description: 101. 對稱二叉樹
 *
 */
public class LeetCode_0101 {

}

// Definition for a binary tree node.
class TreeNode_0101 {
	int val;
	TreeNode_0101 left;
	TreeNode_0101 right;

	TreeNode_0101(int x) {
		val = x;
	}
}

class Solution_0101 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月4日 下午11:34:28 
	 * @param: @param root
	 * @param: @return
	 * @return: boolean
	 * @Description: 1-遞歸校驗；
	 *
	 */
	public boolean isSymmetric(TreeNode_0101 root) {
		if (root == null) {
			return true;
		} else {
			return checkTree(root.left, root.right);
		}
	}

	private boolean checkTree(TreeNode_0101 left, TreeNode_0101 right) {
		// 左右均不為null，且值也相等時繼續遞歸，註意遞歸的鏡像參數
		if (left != null && right != null && left.val == right.val) {
			return checkTree(left.right, right.left) && checkTree(left.left, right.right);
			// 左右均為null時，返回true，該層遞歸結束
		} else if (left == null && right == null) {
			return true;
			// 左右一個為null一個不為null或左右值不等時，返回false，該層遞歸結束
		} else {
			return false;
		}
	}
}