DAY19 Symmetric Tree

第 11 屆 iThome 鐵人賽

DAY 19

自我挑戰組

刷題記錄與人生分享系列第 19 篇

11th鐵人賽 leetcode c javascript

keyhouse12

2019-09-20 09:20:01

880 瀏覽

題目:

https://leetcode.com/problems/symmetric-tree/
判斷一個二元樹是否鏡像，是的話回傳TRUE不是的話回傳FALSE。

解題思路:

利用遞迴尋訪特性，將左節點和右節點相互比較，當條件不符合時直接跳出。
也可以用非遞迴的方式去解，利用堆疊先進後出的觀念去做處理。

C版本:

bool isSymmetric(struct TreeNode* root) {
    return isMirror(root, root);
}

bool isMirror(struct TreeNode *root1, struct TreeNode *root2)
{
	if (root1 == NULL && root2 == NULL)
		return true;
	if (root1 && root2 && root1->val == root2->val)
		return isMirror(root1->left, root2->right) &&
			isMirror(root1->right, root2->left);
	return false;
}

Javascript版本:

var isSymmetric = function(root) {
    if (!root) return true
  
    const stack = []
    stack.push(root.left, root.right)
  
    while (stack.length) {
        const left = stack.pop()
        const right = stack.pop()
    
    if (left === right) continue
    if (!left || !right || left.val !== right.val) return false
    
    stack.push(left.left, right.right)
    stack.push(left.right, right.left)
  }
  return true
};