LeetCode 专题暴击:二叉树的iterative 做法汇总

发布于 2023-05-24  313 次阅读


前言

这个专题用来总结二叉树的iterative做法,那么一般情况下iterative的做法是使用stack来实现,因为stack的特性是LIFO,所以可以用来实现DFS,而queue的特性是FIFO,所以可以用来实现BFS。

知识点回顾

首先我们来复习一下前序遍历,中序遍历,后序遍历的定义:

  • 前序遍历:根节点 -> 左子树 -> 右子树
  • 中序遍历:左子树 -> 根节点 -> 右子树
  • 后序遍历:左子树 -> 右子树 -> 根节点

举一个例子来说就是:

    1
   / \
  2   3
 / \ / \
4  5 6  7
  • 前序遍历:1 2 4 5 3 6 7
  • 中序遍历:4 2 5 1 6 3 7
  • 后序遍历:4 5 2 6 7 3 1

基础类型

↓点击题目就可以直接跳转到leetcode题目页面↓

94. Binary Tree Inorder Traversal

test cases:
image.png

Input: root = [1,null,2,3]
Output: [1,3,2]

Input: root = []
Output: []

Input: root = [1]
Output: [1]

我们先看一下inorder recusive 的做法:


class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        dfs(root)
        return res

那么我们思考一下这个,如何把recursive转变成iterative呢?在中序遍历中,我们可以发现,我们需要先遍历左子树,然后遍历根节点,然后遍历右子树,那么我们可以先把根节点放入stack中,然后一直把左子树放入stack中,直到左子树为空,然后pop出stack中的元素,把元素的值放入res中,然后把root.right放入stack中,然后重复上面的操作。

具体操作就是:

  • 先把root放入stack中
  • 一直把root.left放入stack中,直到root.left为空
  • 然后pop出stack中的元素,把元素的值放入res中
  • 然后把root.right放入stack中,然后重复上面的操作
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        while root or stack: # 这里有两个条件,一个是root != None,一个是stack != []
            while root: # 走到最左边
                stack.append(root)
                root = root.left
            root = stack.pop()
            res.append(root.val)
            root = root.right
        return res

复杂度分析:

  • 时间复杂度:O(n),因为每个节点都会被遍历一次
  • 空间复杂度:O(n),因为stack的大小最大为n

144. Binary Tree Preorder Traversal

test cases:
image.png

Input: root = [1,null,2,3]
Output: [1,2,3]

Input: root = []
Output: []

Input: root = [1]
Output: [1]

我们先看一下preorder recusive 的做法,这个preorder的做法,跟之前的区别不大,只是在使用的时候,先把root.val放入res中,然后再遍历左子树,然后再遍历右子树。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def dfs(root):
            if not root:
                return
            res.append(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return res

那么我们思考一下这个,如何把recursive转变成iterative呢?在前序遍历中,我们可以发现,我们需要先遍历根节点,然后遍历左子树,然后遍历右子树,那么我们可以先把根节点放入stack中,然后一直把左子树放入stack中,直到左子树为空,然后pop出stack中的元素,然后把root.right放入stack中,然后重复上面的操作。

具体操作就是:

  • 先把root放入stack中
  • 一直把root.left放入stack中,直到root.left为空
  • 然后pop出stack中的元素
  • 然后把root.right放入stack中,然后重复上面的操作
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        while root or stack:
            while root:
                res.append(root.val) # 因为前序遍历是先遍历根节点,所以这里先把root.val放入res中
                stack.append(root)
                root = root.left
            root = stack.pop()
            root = root.right
        return res

复杂度分析:

  • 时间复杂度:O(n),因为每个节点都会被遍历一次
  • 空间复杂度:O(n),因为stack的大小最大为n

145. Binary Tree Postorder Traversal

test cases:
image.png

Input: root = [1,null,2,3]
Output: [3,2,1]

Input: root = []
Output: []

Input: root = [1]
Output: [1]

我们先看一下postorder recusive 的做法,这个postorder的做法,跟之前的区别不大,只是在使用的时候,先遍历左子树,然后再遍历右子树,然后再把root.val放入res中。

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            dfs(root.right)
            res.append(root.val)
        dfs(root)
        return res

那么我们思考一下这个,如何把recursive转变成iterative呢?在后序遍历中,我们可以发现,我们需要先遍历左子树,然后遍历右子树,然后遍历根节点,那么我们可以先把根节点放入stack中,然后一直把左子树放入stack中,直到左子树为空,然后pop出stack中的元素,然后把root.right放入stack中,然后重复上面的操作。

具体操作就是:

  • 先把root放入stack中
  • 一直把root.left放入stack中,直到root.left为空
  • 然后pop出stack中的元素
  • 然后把root.right放入stack中,然后重复上面的操作
  • 然后把root.val放入res中
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        while root or stack:
            while root:
                res.append(root.val) # 因为后序遍历是先遍历左子树,然后遍历右子树,然后遍历根节点,所以这里先把root.val放入res中
                stack.append(root)
                root = root.right
            root = stack.pop()
            root = root.left
        return res[::-1]

复杂度分析

  • 时间复杂度:O(n),因为每个节点都会被遍历一次
  • 空间复杂度:O(n),因为stack的大小最大为n

高级类型题

173. Binary Search Tree Iterator

test cases:
image.png

这题描述太复杂了,点到题目里面去看吧。

我们直接来看,这道题怎么使用iterative的方法来做。

首先仔细思考一下,他想要的是什么,他想要的是一个iterator,这个iterator可以一直往下走,然后返回当前的值,然后再往下走,然后再返回当前的值,那么我们可以这样做:

  • 首先我们需要一个stack,然后我们把root放入stack中
  • 然后我们一直把root.left放入stack中,直到root.left为空
  • 然后我们pop出stack中的元素,然后把root.right放入stack中,然后重复上面的操作

那我们来看一下解法和前面的有多相似:

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        while root:
            self.stack.append(root)
            root = root.left

    # @return a boolean, whether we have a next smallest number
    def hasNext(self):
        return True if len(self.stack) else False

    # @return an integer, the next smallest number
    def next(self):
        nxt = self.stack.pop()
        x = nxt.right
        while x:
            self.stack.append(x)
            x = x.left
        return nxt.val

复杂度分析:

  • 时间复杂度:O(n),因为每个节点都会被遍历一次
  • 空间复杂度:O(n),因为stack的大小最大为n

我们再来一道可以使用iterative 来做的题目:

98. Validate Binary Search Tree

test cases:
image.png

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

这道题目,我们可以使用iterative的方法来做,我们可以使用stack来做,具体操作就是:

  • 首先我们需要一个stack,然后我们把root放入stack中
  • 然后我们一直把root.left放入stack中,直到root.left为空
  • 然后我们pop出stack中的元素,然后把root.right放入stack中,然后重复上面的操作
  • 然后我们需要一个pre,来记录上一个节点的值,然后我们每次pop出stack中的元素的时候,我们都需要判断一下,当前的值是否大于pre,如果大于,那么我们就更新pre,然后继续往下走,如果不大于,那么我们就返回False
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        stack = []
        pre = float('-inf')
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if root.val <= pre:
                return False
            pre = root.val
            root = root.right
        return True

复杂度分析:

  • 时间复杂度:O(n),因为每个节点都会被遍历一次
  • 空间复杂度:O(n),因为stack的大小最大为n
做一个平静且愿意倾听的人。
最后更新于 2023-05-24