leetcode二叉树相关算法及题目整理

2021/02/18 leetcode 算法
如果文章图片无法显示,可尝试配置host:修复Github图片资源无法显示问题

二叉树自定义栈前中后序遍历,层序遍历,N叉树遍历,打印二叉树所有路径

1、二叉树前中后遍历

二叉树前中后遍历推荐使用自定义栈进行解题,不要使用递归解题,栈中的元素没有null元素

中序遍历思路:

  • 先将全部的左子节点入栈
  • 弹出栈顶元素item
  • 指针cur指向item右子节点

前序或后序遍历思路:

  • 栈顶节点弹栈,把当点节点value加入到result中
  • 左右子节点分别入栈,注意出栈顺序需要保证对应的遍历顺序(前序入栈:中左右->先右后左;后序入栈:左右中->先右后左)

二叉树中序遍历

leetcode-94

from typing import List
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        cur = root
        res = []
        while stack or cur:
            if cur:  # 把所有左侧节点添加到栈中
                stack.append(cur)
                cur = cur.left
            else:  # 弹栈,遍历右侧节点
                item = stack.pop()
                res.append(item.val)
                cur = item.right
        return res

二叉树前序遍历

leetcode-144

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Definition for a binary tree node.
from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []

        stack, result = [root], []

        while stack:
            item = stack.pop()
            result.append(item.val)
            # 入栈先右后左,保证出栈时的顺序为先左后右
            if item.right: stack.append(item.right)
            if item.left: stack.append(item.left)
        return result

if __name__ == '__main__':
    A = TreeNode(1)
    B = TreeNode(2)
    C = TreeNode(3)

    A.left = B
    A.right= C

    s = Solution()
    result = s.preorderTraversal(A)
    print(result)

二叉树后序遍历

leetcode-145

from typing import List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        stack, result = [root], []

        while stack:
            item = stack.pop()
            result.append(item.val)
            if item.left: stack.append(item.left)
            if item.right: stack.append(item.right)
        return result[::-1]

2、N叉树的前序遍历

和二叉树的前序遍历思路基本类似,只是在添加子节点部分略有修改

# Definition for a Node.
from typing import List


class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children


class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root: return []
        stack, result = [root], []

        while stack:
            item = stack.pop()
            result.append(item.val)
            if item.children: stack.extend(item.children[::-1])

        return result

3、二叉树的所有路径

from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        result = []

        def dfs(root, path):
            if root.left is None and root.right is None:  # 子节点
                path += str(root.val)
                result.append(path)

            else:
                path += str(root.val)+"->"
                if root.left:dfs(root.left,path)
                if root.right:dfs(root.right,path)

        if root:
            dfs(root, "")
        return result

4、层序遍历

层序遍历遍历的关键点之一是需要记录队列中的结点数量,用于划分不同的层

4-1 二叉树的深度

原题地址:剑指 Offer 55 - I. 二叉树的深度

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

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

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

示例:
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

解题思路:

利用广度优先遍历思想,进行二叉树的层序遍历,每遍历一层深度+1,这道题的确不是很难leetcode上标注的为easy

import queue

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        dep = 0
        q = queue.Queue()
        q.put(root)
        while q.empty() is False:
            nodes_len = q.qsize()
            for i in range(nodes_len):
                node = q.get()
                if node.left: q.put(node.left)
                if node.right: q.put(node.right)
            dep += 1
        return dep

4-2 二叉树之字形遍历

原题地址:剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,
第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果:
[
  [3],
  [20,9],
  [15,7]
]
提示:
节点总数 <= 1000

解题思路:层序遍历的变形,在偶数层,添加倒序列表,单数层正序列表

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Definition for a binary tree node.
from typing import List
import queue


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# -- BEGIN--
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        """之字形遍历"""
        if root is None: return []
        result = []
        q = queue.Queue()
        q.put(root)
        count = 1
        level = 1
        while not q.empty():
            new_count = 0
            tmp = []
            for _ in range(count):
                item = q.get()
                tmp.append(item.val)
                if item.left is not None:
                    q.put(item.left)
                    new_count += 1
                if item.right is not None:
                    q.put(item.right)
                    new_count += 1
            count = new_count
            if level % 2 != 0:
                result.append(tmp)
            else:
                result.append(tmp[::-1])
            level += 1
        return result
# -- END --

if __name__ == '__main__':
    A = TreeNode(1)
    B = TreeNode(2)
    C = TreeNode(3)
    D = TreeNode(4)
    E = TreeNode(5)

    A.left = B
    A.right = C

    C.left = D
    C.right = E

    s = Solution()
    result = s.levelOrder(A)
    print(result)

4-3 序列化二叉树

原题地址:剑指 Offer 37. 序列化二叉树

请实现两个函数,分别用来序列化和反序列化二叉树。
    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

解题思路:利用二叉树的层序遍历,把每一层的节点都放到列表中(包含最后一层),注意题目中的意思是能够实现序列化和反序列化函数即可,不必在意序列化之后的树的结点列表与所给出的不同。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Definition for a binary tree node.
import collections
from queue import Queue


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Codec:
    def serialize(self, root):
        """
        二叉树层序遍历
        :param root:
        :return:
        """
        if not root: return "[]"
        res = []
        q = Queue()
        q.put(root)
        while not q.empty():
            cur = q.get()
            if cur:
                res.append(str(cur.val))
                # 存放下一层节点 none节点也需要存放
                q.put(cur.left)
                q.put(cur.right)
            else:
                res.append("null")
        return '[' + ','.join(res) + ']'

    def deserialize(self, data):
        if data == "[]": return
        vals, i = data[1:-1].split(','), 1
        root = TreeNode(int(vals[0]))
        queue = collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            if vals[i] != "null":
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            if vals[i] != "null":
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1
        return root


if __name__ == '__main__':
    a = TreeNode(1)

    b = TreeNode(2)
    c = TreeNode(3)

    d = TreeNode(4)
    e = TreeNode(5)

    a.left = b
    a.right = c

    c.left = d
    c.right = e

    res = Codec().serialize(a)
    print(res)

5、平衡二叉树

原题地址:剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。
如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。 
 示例 1: 
 给定二叉树 [3,9,20,null,null,15,7] 
     3
   / \
  9  20
    /  \
   15   7 

 返回 true 。 
示例 2: 
 给定二叉树 [1,2,2,3,3,null,null,4,4] 
        1
      / \
     2   2
    / \
   3   3
  / \
 4   4
 返回 false 。 
 限制:
 1 <= 树的结点个数 <= 10000
 注意:本题与主站 110 题相同:https://leetcode-cn.com/problems/balanced-binary-tree/ 

解题思路:

二叉树深度的判断和二叉树遍历的结合体,总体思路就是,判断每一个节点的左右子树的最大深度只差不超过1,空节点的深度为0

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def dfs(cur):
            # 获取当前节点的左右子树高度
            left_dep, right_dep = self.maxDepth(cur.left), self.maxDepth(cur.right)
            # 判断左子树是否平衡
            left_res = dfs(cur.left) if cur.left else True
            # 判断右子树是否平衡
            right_res = dfs(cur.right) if cur.right else True
            
            # 最终判断 当前子树平衡并且左右子树平衡当前二叉树才为平衡二叉树
            return abs(left_dep - right_dep) <= 1 and left_res and right_res  

        if not root: return True
        return dfs(root)

    def maxDepth(self, root):
        if not root: return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

6、二叉搜索树

6-1 二叉搜索树的第k大节点

原题地址:剑指 Offer 54. 二叉搜索树的第k大节点

解题思路:考察二叉搜索树特性和二叉树中序遍历

二叉搜索树左中右遍历为小中大,因此把右节点看成左节点,按照中序遍历的变形,进行遍历k次,后直接返回对应值即可

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

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        stack = []
        cur = root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.right
            item = stack.pop()
            k -= 1
            if k == 0: return item.val
            cur = item.left

6-2 二叉搜索树与双向链表

原题地址:剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。
要求不能创建任何新的节点,只能调整树中节点指针的指向。

解题思路:

先建立一个哨兵节点pre,利用dfs遍历处理,主要处理cur节点。

注意最后要把首尾节点进行连接

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# -- BEGIN --
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if not cur: return
            dfs(cur.left)
            # 处理中间cur节点
            if self.pre:
                self.pre.right = cur
                cur.left = self.pre
            else:
                self.head = cur
            self.pre = cur
            dfs(cur.right)

        if not root: return
        self.pre = None
        dfs(root)
        # 遍历拼接完毕,构建首尾连接,self.pre为最后一个遍历的节点,
        self.head.left = self.pre
        self.pre.right = self.head
        return self.head
# -- END --

# 用于debug使用,输出最终结果
def list2arr(root):
    result = []
    my_set = set()
    cur = root
    while cur and cur not in my_set:
        my_set.add(cur)
        result.append(cur.val)
        cur = cur.right
    return result


if __name__ == '__main__':
    a = Node(4)
    b = Node(2)
    c = Node(5)
    d = Node(1)
    e = Node(3)

    a.left = b
    a.right = c

    b.left = d
    b.right = e
    res = Solution().treeToDoublyList(a)
    print(list2arr(res))

6-3 二叉搜索树的后序遍历序列

原题地址:剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。
如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同

解题思路:

二叉搜索树的特点是:左子树 < root < 右子树 后序遍历时采用的是:左 右 root , 故可不断对数组进行划分,看左子树和右子树是否符合搜索树顺序。

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        def recur(i, j):
            if i >= j: return True
            cur = i
            while postorder[cur] < postorder[j]: cur += 1  # 划分左子树:[i:cur]
            left = cur

            while postorder[cur] > postorder[j]: cur += 1  # 划分右子树 [left:cur]
            # 此时cur应该指向数组中最后一个节点:root
            return cur == j and recur(i, left-1) and recur(left, j-1)

        return recur(0, len(postorder) - 1)

7、树的子结构

原题地址:剑指 Offer 26. 树的子结构

解题思路:首先构建一个isEqu(cur,target)用来判断当前子树和目标子树是否相同,如果target为null,返回true

然后遍历当前树,当cur.val == b.target时,进行对比,否则分别对比左右子树

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


# 遍历A树
# 判断是否是子结构

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        """判断B树是否A树的子结构"""
        result = False
        if A is not None and B is not None:
            if A.val == B.val:
                result = self.isEqu(A, B)
            if result is False:
                result = self.isSubStructure(A.left, B)
            if result is False:
                result = self.isSubStructure(A.right, B)
        return result
    
	# 判断B树是否和A树相同,默认B为null,返回true
    def isEqu(self, A: TreeNode, B: TreeNode) -> bool:
        if B is None: return True
        if A is None: return False
        if A.val != B.val: return False
        return self.isEqu(A.left, B.left) and self.isEqu(A.right, B.right)

8、二叉树的镜像

原题地址:剑指 Offer 27. 二叉树的镜像

用于理解递归,只要理解了递归,这道题就非常简单

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


class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if root is None: return
        root.left, root.right = self.mirrorTree(root.right),self.mirrorTree(root.left)
        return root
class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if root is None: return
        q = queue.Queue()
        q.put(root)
        while not q.empty():
            item = q.get()
            if item.left: q.put(item.left)
            if item.right: q.put(item.right)
            # 翻转子节点
            item.left, item.right = item.right, item.left
        return root

9、对称的二叉树

原题地址:剑指 Offer 28. 对称的二叉树

# 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 isSymLoop(left, right):
            # 都为空,有一个为空,都不为空
            if not left and not right: return True
            if not left or not right or left.val != right.val: return False
            return isSymLoop(left.left, right.right) and isSymLoop(left.right, right.left)

        return isSymLoop(root.left, root.right) if root else True

10、二叉树中和为某一值的路径

原文地址:剑指 Offer 34. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。
从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树,以及目标和 sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:
[
   [5,4,11,2],
   [5,8,4,5]
]

题解思路:

二叉树路径遍历的变种,需要在dfs中添加当前路径的sum值

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from typing import List
import copy

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 二叉树路径遍历变种
# 图的遍历:BFS/DFS
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        if not root : return []
        result = []

        def dfs(root, path, ssum):
            mypath = copy.deepcopy(path)
            if not root.left and not root.right: # 叶子节点,判断路径是否相等
                if ssum+root.val == sum:
                    mypath.append(root.val)
                    result.append(mypath)
            else:
                mypath.append(root.val)
                ssum += root.val
                if root.left: dfs(root.left, mypath, ssum)
                if root.right: dfs(root.right, mypath, ssum)

        dfs(root, [], 0)
        return result

公众号:豆仔gogo

golang、算法、后端知识、面试手册

豆仔gogo

Search

    公众号:豆仔gogo

    豆仔gogo

    Post Directory