Leetcode 101. Symmetric Tree

Symmetric Tree
image 22

Symmetric Tree :

給定一個二元樹，檢查是否左右對稱(Symmetric)

Python

遞迴法 :

如果左右子樹都為null，表示兩者相等為null，回傳true。如果其中一個子樹圍null，則不對稱，回傳false。之後對稱的樹應該符合以下3點 :

  1. 左子樹根的值=右子樹根的值
  2. 左子樹的左子樹要和右子樹的右子樹對稱
  3. 左子樹的右子樹要和右子樹的左子樹對稱
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        return self.sym(root.left, root.right)
        
    def sym(self, l: TreeNode, r: TreeNode) -> bool:
        if not l and not r: return True
        if not l or not r: return False
        return l.val == r.val and self.sym(l.left, r.right) and self.sym(l.right, r.left)

迭代法 :

  1. 首先判斷root，沒有問題的話，root的左右放到Queue裡面。
  2. 此時Queue裡面有值，做遞迴(判斷l.left, r.right跟l.right, r.left)，將這四個節點依序放至Queue中。
  3. 重複執行直到Queue空掉或當中判斷為假的狀況即回傳假。
  4. 如果Queue空掉了離開循環，代表結果為真，回傳真值。
from collections import deque
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        queue = deque([(root.left, root.right)])
        while queue:
            node1, node2 = queue.popleft()
            if not node1 and not node2:
                continue
            if node1 and node2 and node1.val == node2.val:
                queue.append((node1.left, node2.right))
                queue.append((node1.right, node2.left))
            else:
                return False
        return True

C++

遞迴法 :

首先檢查整個樹是否對稱，然後檢查每個子樹是否對稱。對於每個子樹，比較左右子樹的值是否相等，然後遞歸地檢查左子樹的左子樹是否等於右子樹的右子樹，以及左子樹的右子樹是否等於右子樹的左子樹。如果左右子樹都為 nullptr，則返回 true，因為這樣不會影響樹的對稱性。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        return isSymmetric(root->left, root->right);
    }
    
    bool isSymmetric(TreeNode* leftNode, TreeNode* rightNode) {
        if (leftNode == nullptr && rightNode == nullptr) {
            return true;
        }
        if (leftNode == nullptr || rightNode == nullptr) {
            return false;
        }
        if (leftNode->val != rightNode->val) {
            return false;
        }
        return isSymmetric(leftNode->left, rightNode->right) && isSymmetric(leftNode->right, rightNode->left);
    }
};

這個解法也是基於對稱性的原理，使用隊列來存儲要比較的節點，首先將左子樹和右子樹的根節點加入隊列，然後每次從隊列中取出兩個節點進行比較。如果兩個節點都為空，則繼續循環，如果一個節點為空而另一個節點非空，則返回 false。如果兩個節點都非空但是值不相等，則返回 false。如果兩個節點都非空且值相等，則將左子樹的左子節點和右子樹的右子節點、左子樹的右子節點和右子樹的左子節點加入隊列中，繼續循環，直到隊列為空。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        
        while (!q.empty()) {
            TreeNode* leftNode = q.front();
            q.pop();
            TreeNode* rightNode = q.front();
            q.pop();
            
            if (leftNode == nullptr && rightNode == nullptr) {
                continue;
            }
            if (leftNode == nullptr || rightNode == nullptr) {
                return false;
            }
            if (leftNode->val != rightNode->val) {
                return false;
            }
            
            q.push(leftNode->left);
            q.push(rightNode->right);
            q.push(leftNode->right);
            q.push(rightNode->left);
        }
        
        return true;
    }
};