4.15 二刷这道微软面试题,把讨论里的解法都理了一遍!

zzzrf 26天前 34

这里是题目描述

样例 1

输入: {1,2,2,3,4,4,3}
输出: true
解释:
    1
   / \
  2   2
 / \ / \
3  4 4  3
{1,2,2,3,4,4,3}这棵二叉树是对称的

样例 2

输入: {1,2,2,#,3,#,3}
输出: false
解释:
    1
   / \
  2   2
   \   \
   3    3
很显然这棵二叉树并不对称

用递归和迭代的方法来解决这个问题(2 种解法)

代码

···
使用分治法 Divide Conquer 的版本
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: root of the given tree
    @return: whether it is a mirror of itself 
    """
    def isSymmetric(self, root):
        if not root:
            return True
        return self._is_symmetric(root.left, root.right)
        
    def _is_symmetric(self, left_root, right_root):
        if left_root is None and right_root is None:
            return True
        if left_root is None or right_root is None:
            return False
        if left_root.val != right_root.val:
            return False
            
        left = self._is_symmetric(left_root.left, right_root.right)
        right = self._is_symmetric(left_root.right, right_root.left)
        return left and right

使用 Iteration 的版本

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: root of the given tree
    @return: whether it is a mirror of itself 
    """
    
    def isSymmetric(self, root):
        inorder = self.inorder(root, reverse=False)
        reverse_inorder = self.inorder(root, reverse=True)
        if inorder != reverse_inorder:
            return False
            
        preorder = self.preorder(root, reverse=False)
        reverse_preorder = self.preorder(root, reverse=True)
        return preorder == reverse_preorder
        
    def get_left(self, node, reverse):
        if reverse:
            return node.right
        return node.left
        
    def get_right(self, node, reverse):
        if reverse:
            return node.left
        return node.right
        
    def preorder(self, root, reverse):
        stack = [root]
        order = []
        while stack:
            node = stack.pop()
            order.append(node.val)
            right = self.get_right(node, reverse)
            if right:
                stack.append(right)
            left = self.get_left(node, reverse)
            if left:
                stack.append(left)
        return order
        
    def inorder(self, root, reverse):
        stack = []
        while root is not None:
            stack.append(root)
            root = self.get_left(root, reverse)
            
        order = []
        while stack:
            node = stack[-1]
            order.append(node.val)
            right = self.get_right(node, reverse)
            if right is not None:
                node = right
                while node is not None:
                    stack.append(node)
                    node = self.get_left(node, reverse)
            else:
                stack.pop()
                while stack and self.get_right(stack[-1], reverse) == node:
                    node = stack.pop()
        
        return order

使用 BFS 算法的版本

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: root of the given tree
    @return: whether it is a mirror of itself 
    """
    def isSymmetric(self, root):
        queue = [root]
        while queue:
            next_queue = []
            for i in range(len(queue)):
                if queue[i] is None:
                    continue
                next_queue.append(queue[i].left)
                next_queue.append(queue[i].right)
            if not self.is_mirror(next_queue):
                return False
            queue = next_queue
        return True
        
    def is_mirror(self, queue):
        left, right = 0, len(queue) - 1
        while left < right:
            if not self.is_same(queue[left], queue[right]):
                return False
            left, right = left + 1, right - 1
        return True
        
    def is_same(self, node1, node2):
        if node1 and node2:
            return node1.val == node2.val
        return node1 is None and node2 is None
最新回复 (0)
  • 游客
    2
返回