实习之路记录_牛客博客

# 方法一 递归解法 前序后序中序都是相同的套路
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def preorder(root: TreeNode):
            # 结束条件：节点为null,则结束
            if not root:
                return
            # 遍历根节点
            res.append(root.val)
            # 遍历
            preorder(root.left)
            preorder(root.right)
        res = list()
        preorder(root)
        return res
# 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次
# 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(\log n)，最坏情况下树呈现链状，为 O(n)。

中序

# 方法一 递归法
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        def inorder(root: TreeNode):
            if not root:
                return
            # 先遍历左子树
            inorder(root.left)
            # 根节点
            res.append(root.val)
            # 遍历右子树
            inorder(root.right)
        res = list()
        inorder(root)
        return res

后序

# 解法一 递归法
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        def postorder(root:TreeNode):
            if not root:
                return
            postorder(root.left)
            postorder(root.right)
            res.append(root.val)
        res = list()
        postorder(root)
        return res

迭代解法：

递归的时候隐式地维护了一个栈，而在迭代的时候需要显式地将这个栈模拟出来。这个难度比递归要难一些

前序：

# 方法二 迭代解法
# 使用栈来递归
# https://www.bilibili.com/video/BV1dA411L7Mj  这个up讲得太好了！！！一下子明白了
# 1. 初始化栈，将根节点入栈
# 2. 当栈不为空时：
# 弹出栈顶元素 node，并将值添加到结果中；
# 如果 node 的右子树非空，将右子树入栈；
# 如果 node 的左子树非空，将左子树入栈

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 特例判断
        if not root:
            return
        # 把根节点压入栈中
        stack = [root]
        # 结果列表
        ans = []
        # 当栈不为空，也就是树还没遍历完
        while stack:
            # 弹出栈顶元素
            node = stack.pop()
            ans.append(node.val)
            # 先把右子树压进去，先进后出
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return ans

中序

# 方法二 迭代法 使用一个固定的模板
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        ans = []
        # 都是要先把根节点压进去
        cur, stack = root, []
        # 只要当前节点或者栈有一个不是空就继续遍历
        while cur or stack:
            while cur:
                # cur 入栈
                stack.append(cur)
                # 找到当前最左端的孩子
                cur = cur.left
            # 弹出栈顶元素
            tmp = stack.pop()
            # 加入结果
            ans.append(tmp.val)
            # 弹出栈中叶节点的父节点，当左子树完全遍历完就会遍历右子树
            cur = tmp.right

后序没搞懂，需要一个pre节点来判断是都遍历？？

实习之路记录

一、面经汇总：

1. 网易、滴滴、爱奇艺、平安科技、新浪 算法面经

2. 深信服、腾讯、字节 开发面经

3. C++ 面试基础总结

4. 机器学习面经

5. 开发工程师面经

6. C++面试总结

二、知识点准备：

一些值得参考的链接：

三、常见的手撕代码：

1. 二叉树的遍历

1. 网易、滴滴、爱奇艺、平安科技、新浪算法面经

2. 深信服、腾讯、字节开发面经