Leetcode二叉树算法

 

LeetCode-python 101.对称二叉树

 

 

难度：简单       类型： 二叉树

 

---

 

给定一个二叉树，检查它是否是镜像对称的。

 

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

 

    1
   / 
  2   2
 /  / 
3  4 4  3

 

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

 

    1
   / 
  2   2
      
   3    3

 

解题思路

 

---

 

将该问题转化为根节点的左子树和右子树是否是镜像对称的

 

两个树互为镜像的条件是：

 

1. 它们的根节点具有相同的值
2. 每个树的左子树都与另一个树的右子树镜像对称

 

代码实现

 

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

class Solution:
    def convers(self,p,q):
        if p == None and q == None:
            return True
        elif p == None or q == None:
            return False
        elif p.val == q.val:
            return self.convers(p.left, q.right) and self.convers(p.right, q.left)
        else:
            return False

    def isSymmetric(self, root: TreeNode) -> bool:
        if root:
            return self.convers(root.left,root.right)
        else:
            return True

 

LeetCode-python 104.二叉树的最大深度

 

难度：简单       类型： 二叉树，递归

---

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

示例
给定二叉树 [3,9,20,null,null,15,7]

    3
   / 
  9  20
    /  
   15   7

解题思路

---

最大的深度是左子树或右子树中深度中更大的一个+1，递归的在子树的子树中寻找

代码实现

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

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        else:
            l = self.maxDepth(root.left)
            r = self.maxDepth(root.right)
            return max(l,r)+1