递归与二叉树

例题

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        node=root
        if node is None:
            return 0
        l_depth=self.maxDepth(node.left)
        r_depth=self.maxDepth(node.right)
        return max(l_depth,r_depth)+1

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q
        return p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def aa(p:Optional[TreeNode],q:Optional[TreeNode])->bool:
            if p is None or q is None:
                return p is q
            return p.val==q.val and aa(p.left,q.right) and aa(p.right,q.left)
        return aa(root.left,root.right)

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_height(node: Optional[TreeNode]) -> int:
            if node is None: return 0
            left_h = get_height(node.left)
            if left_h == -1: return -1  # 提前退出，不再递归
            right_h = get_height(node.right)
            if right_h == -1 or abs(left_h - right_h) > 1: return -1
            return max(left_h, right_h) + 1
        return get_height(root) != -1

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans=[]
        def f(node,depth):
            if node is None:
                return
            if depth==len(ans):
                ans.append(node.val)
            f(node.right,depth+1)
            f(node.left,depth+1)
        f(root,0)
        return ans