[leetcode/lintcode 题解]算法面试高频题详解: 对称树

简介: [leetcode/lintcode 题解]算法面试高频题详解: 对称树

描述
给定二叉树,返回它是否是自身的镜像(即这棵二叉树是否对称)。

在线评测地址:领扣题库官网

样例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

更多题解参考:九章官网solution

相关文章
|
1天前
|
算法 数据可视化 Python
Python中的决策树算法探索
Python中的决策树算法探索
|
2天前
|
人工智能 算法 Java
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。
|
7天前
|
机器学习/深度学习 算法 前端开发
决策树与随机森林算法在分类问题中的应用
本文探讨了决策树和随机森林两种监督学习算法,它们在分类任务中表现出强大的解释性和预测能力。决策树通过特征测试进行分类,构建涉及特征选择、树生成和剪枝。随机森林是集成学习方法,通过构建多棵决策树并汇总预测结果,防止过拟合。文中提供了Python代码示例,展示如何使用sklearn构建和应用这些模型,并讨论了参数调优和模型评估方法,如交叉验证和混淆矩阵。最后,强调了在实际问题中灵活选择和调整模型参数的重要性。
29 4
|
8天前
|
存储 机器学习/深度学习 算法
使用决策树算法预测隐形眼镜类型
使用决策树算法预测隐形眼镜类型
20 2
|
8天前
|
存储 算法 Python
决策树算法
决策树算法
11 2
|
9天前
|
SQL 算法 大数据
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
|
9天前
|
存储 算法 搜索推荐
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
|
9天前
|
SQL 大数据 数据挖掘
深入解析力扣178题:分数排名(DENSE_RANK详解及模拟面试问答)
深入解析力扣178题:分数排名(DENSE_RANK详解及模拟面试问答)
|
9天前
|
SQL 算法 大数据
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
|
9天前
|
存储 算法 数据挖掘
力扣174题动态规划:地下城游戏(含模拟面试)
力扣174题动态规划:地下城游戏(含模拟面试)