LeetCode Symmetric Tree

LeetCode解題之Symmetric Tree

原題

判斷一棵樹是否是鏡面對稱的。最好同時提供遞歸和迭代的解法。

注意點：

例子：

輸入:

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

輸出: True

輸入:

    1
   / \
  2   2
   \   \
   3    3

輸出: False

解題思路

看一棵二叉樹是否對稱，就要首先看根節點的左右節點A和B是否有相同的值，如果A和B的值相等，那麼要繼續判斷A的左節點和B的右節點以及A的右節點和B的左節點是否對稱，通過這樣的方式來遞歸得到結果。用迭代方法來解決的話，就把要判斷是否對稱的點按序（注意需要判斷哪些節點是否相等）放到兩個棧中，不斷出棧和壓棧來判斷。

AC源碼

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    # Solve it recursively
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self._isSymmetric(root.left, root.right)

    def _isSymmetric(self, left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        return self._isSymmetric(left.left, right.right) and self._isSymmetric(left.right, right.left)

    # Solve it iteratively
    def isSymmetric_iterate(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        stack1, stack2 = [], []
        stack1.append(root.left)
        stack2.append(root.right)
        while stack1 and stack2:
            size1 = len(stack1)
            size2 = len(stack2)
            if size1 != size2:
                return False
            for __ in range(size1):
                curr1, curr2 = stack1.pop(), stack2.pop()
                if not curr1 and not curr2:
                    continue
                if not curr1 or not curr2:
                    return False
                if curr1.val != curr2.val:
                    return False
                stack1.append(curr1.left)
                stack1.append(curr1.right)
                stack2.append(curr2.right)
                stack2.append(curr2.left)
        return not stack1 and not stack2

if __name__ == "__main__":
    None