[LeetCode] 101. Symmetric Tree

轉自LeetCode

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

<Solution>

這題是要看一個 binary tree 是否有對稱性

題目有說使用 recursive 和 iterative 兩種解法來解

先來看 recursive 的解法

想法和 Same Tree 中的 recursive 解法一樣

變化的地方在於，不是檢查兩個樹的左子樹和右子樹是否一樣

而是檢查 node1 的左子樹和 node2 的右子樹，以及 node1 的右子樹和 node2 的左子樹是否一樣

code 如下
c++

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool isSymmetric(TreeNode* root) {
	return checkSymmetric(root, root);
	}
	bool checkSymmetric(TreeNode *p, TreeNode *q) {
	if(!p && !q) {
	return true;
	}
	if((!p || !q) || (p->val != q->val)) {
	return false;
	}
	return checkSymmetric(p->left, q->right) && checkSymmetric(p->right, q->left);
	}
	};

view raw checkSymmetricBinaryTree_1.cpp hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun isSymmetric(root: TreeNode?): Boolean {
	return check(root, root)
	}
	fun check(p: TreeNode?, q: TreeNode?): Boolean {
	return when {
	p == null && q == null -> true
	p == null || q == null -> false
	p!!.`val` != q!!.`val` -> false
	else -> check(p!!.left, q!!.right) && check(p!!.right, q!!.left)
	}
	}
	}

view raw symmetric_tree.kt hosted with ❤ by GitHub

再來看 iterative 的解法

想法一樣，檢查node1 的左子樹和 node2 的右子樹，以及 node1 的右子樹和 node2 的左子樹是否一樣

只是這次準備一個 queue 去存 node (不一定要用 queue，用 list 或是 stack 都可以)

每次就丟對稱的 node 進去 queue，然後檢查時，一次拿兩個 node 出來檢查

code 如下
c++

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool isSymmetric(TreeNode* root) {
	queue<TreeNode *> nodeQue;
	nodeQue.push(root);
	nodeQue.push(root);
	while(!nodeQue.empty()) {
	TreeNode *tmpNode1 = nodeQue.front();
	nodeQue.pop();
	TreeNode *tmpNode2 = nodeQue.front();
	nodeQue.pop();
	if(!tmpNode1 && !tmpNode2) {
	continue;
	}
	else if((!tmpNode1 || !tmpNode2) || (tmpNode1->val != tmpNode2->val)) {
	return false;
	}
	//> push node into queue
	nodeQue.push(tmpNode1->left);
	nodeQue.push(tmpNode2->right);
	nodeQue.push(tmpNode1->right);
	nodeQue.push(tmpNode2->left);
	}
	return true;
	}
	};

view raw checkSymmetricBinaryTree_2.cpp hosted with ❤ by GitHub