iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 19
0

題目:

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
};

程式Github分享:

https://github.com/SIAOYUCHEN/leetcode

相似主題分享:

https://ithelp.ithome.com.tw/users/20100009/ironman/2500
https://ithelp.ithome.com.tw/users/20113393/ironman/2169
https://ithelp.ithome.com.tw/users/20107480/ironman/2435
https://ithelp.ithome.com.tw/users/20107195/ironman/2382
https://ithelp.ithome.com.tw/users/20119871/ironman/2210
https://ithelp.ithome.com.tw/users/20106426/ironman/2136

本日分享:

Remember what to remember, forget what to forget. Change what can be changed, accept what can not be changed
記住該記住的,忘記該忘記的。改變能改變的,接受不能改變的


上一篇
DAY18 Same Tree
下一篇
DAY20 Maximum Depth of Binary Tree
系列文
刷題記錄與人生分享34
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言