二叉树练习

leetcoed 94小试牛刀

二叉树的中序遍历（递归版）

首先判断当前节点是否为空，如果为空就返回空列表(题目要求)

然后我们直接返回对象中的根左节点 + [根中] + 根右节点 #都为列表的形式

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

二叉树DFS(深度优先搜索)

求最大深度 leetcode 104(递归版)

首先我们判断根节点是否为空如果为空我们返回0(题目要求)

然后我们就可以直接递归求二叉树的最大深度了直接返回

深度层级:
第1层: maxDepth(3) ← 开始
第2层:   ├── maxDepth(9)
第3层:   │     ├── maxDepth(None) → 返回0
第3层:   │     └── maxDepth(None) → 返回0
第2层:   └── maxDepth(20)
第3层:         ├── maxDepth(15)
第4层:         │     ├── maxDepth(None) → 返回0
第4层:         │     └── maxDepth(None) → 返回0
第3层:         └── maxDepth(7)
第4层:               ├── maxDepth(None) → 返回0
第4层:               └── maxDepth(None) → 返回0

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0 
        return 1 + max(self.maxDepth(root.left),self.maxDepth(root.right))

解释

为什么要+1：是因为遍历到了当前的节点，所以就存在，存在说明当前的子节点算一个深度所以 +1

if root is None: return 0 : 表示当前递归到了最下边所有返回一个 0 表示没有了 (结束条件)

self.maxDepth(root.left)递归遍历自己的左子树

self.maxDepth(root.right)递归遍历自己的右子树

最后使用max()函数进行计算可得最大深度DFS

反转二叉树 leetcode 226

代码

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

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root:
            root.left,root.right = self.invertTree(root.right),self.invertTree(root.left)
        return root