运用递归解决二叉树问题_递归思想解决二叉树问题的优缺点

二叉树的各种遍历方法可以参考我的博客  二叉树的各种遍历方法。

二叉树的最大深度

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

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

说明: 叶子节点是指没有子节点的节点。

# 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:
        res = 0
        def dfs(root,d):
            if not root:return
            nonlocal res
            res = max(res,d)
            dfs(root.left,d+1)
            dfs(root.right,d+1)
        dfs(root,1)
        return res

对称的二叉树

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def sym(node1,node2):
            if not node1 and not node2:
                return True
            if not node1 or not node2:
                return False
            return node1.val==node2.val and sym(node1.left,node2.right) and sym(node1.right,node2.left)
        if not root:
            return True
        return sym(root.left,root.right)

路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    def hasPathSum(self, root: TreeNode, sumn: int) -> bool:
        def dfs(root,tar):
            if not root:return False
            tar = tar - root.val
            if tar==0 and not root.left and not root.right:
                return True
            return dfs(root.left,tar) or dfs(root.right,tar)
        return dfs(root,sumn)