大厂常考算法题之二叉树

举报
程序员学长 发表于 2021/12/12 22:41:25 2021/12/12
【摘要】 二叉树 全文概览 基础知识树是一种非常重要的非线性数据结构，而二叉树是一种特殊的树。二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。 二叉树的分类 满二叉树满二叉树：如果一棵二叉树只有度为0的结点...

二叉树

全文概览

image-20211208102156580

基础知识

树是一种非常重要的非线性数据结构，而二叉树是一种特殊的树。

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

二叉树的分类

满二叉树

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树被称为满二叉树。

image-20211207165513029

完全二叉树

完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。

image-20211207165540509

二叉查找树

二叉查找树又被称为是二叉搜索树，它是一棵空树，或者是具有下列性质的二叉树：

  • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

  • 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

  • 左、右子树也分别为二叉查找树；

image-20211207170733856

平衡二叉树

平衡二叉树（Balanced Binary Tree）又被称为AVL树，它是一棵特殊的二叉查找树。它具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

它很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。

image-20211207170844952

二叉树的存储方式

二叉树的存储方式分为两种，分别为链式存储和顺序存储。

链式存储

二叉树的链式存储是用链表来实现的，对于链表中的每个结点，它不仅包含了数据域，还包含了两个指针域，分别指向其左、右孩子结点，如下图所示。

image-20211207171832225

image-20211207171755636

顺序存储

二叉树的顺序存储是用数组来实现的，它用一组连续的存储单元来存储二叉树中的数据元素。为了能反映出结点之间的逻辑关系。可以采用编号的方法，即对二叉树按完全二叉树进行编号，其中编号为 i 的结点存储在数组中下标为 i 的分量中。

我们可以很容易知道，对于下标为 i 的父节点，其左、右孩子的下标分别为 2 * i + 1 和 2 * i + 2。

image-20211207172254486

二叉树的遍历

二叉树的遍历主要有两种遍历方式，即深度优先遍历和广度优先遍历。

深度优先遍历（Depth First Search，简称DFS）

二叉树的深度优先遍历是指从根节点出发，然后对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。它可以细分为前序遍历、中序遍历和后续遍历。

  • 前序遍历

    先访问根节点，然后遍历其左子树，最后遍历其右子树

  • 中序遍历

    先遍历其左子树，然后访问根节点，最后遍历其右子树。

  • 后续遍历

    先遍历其左子树，然后遍历其右子树，最后访问根节点。

image-20211207172928008

广度优先遍历（Breath First Search，简称BFS）

广度优先遍历是指从根节点出发，按层一层层的去遍历二叉树的节点。

广度优先遍历也叫做层序遍历。

image-20211207173018698

实现二叉树的先序、中序和后序遍历

LeetCode 144. 二叉树的前序遍历

LeetCode 94. 二叉树的中序遍历

LeetCode 145. 二叉树的后序遍历

问题描述

给定一个二叉树，分别按照二叉树的先序、中序和后序打印所有节点。

要求：空间复杂度是O(n)，时间复杂度是O(n)。

示例：

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [[1,2,3],[1,3,2],[3,2,1]]

分析问题

拿到这个问题时，首先我们需要知道什么是先序遍历、中序遍历和后序遍历。

  1. 先序遍历：按照根节点 -> 左子树 -> 右子树的顺序来遍历这颗树，而访问左、右子树时，也采用同样的顺序进行遍历，直到遍历完整棵树。

  2. 中序遍历：按照左子树 -> 根节点 -> 右子树的顺序来遍历这棵树，而访问左、右子树时，也采取同样的顺序进行遍历，直到遍历完整颗树。

  3. 后续遍历：按照左子树 -> 右子树 -> 根结点的顺序来遍历这棵树，而访问左、右子树时，也采取同样的顺序进行遍历，直到遍历完整颗树。

根据二叉树的先序、中序、后序的定义，我们可以很直观的想到采用递归的方式来遍历整棵树。下面我们来看一下如何使用递归的方式实现二叉树的先序、中序和后序遍历。

递归

image-20210925154017905

使用递归来遍历，当遇到根节点的左子树或右子树不为空时，我们就把它的左子树或右子树再当做一颗完整的树来处理。

为了方便理解，我们先看一下结点的定义。

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

先序遍历

    def preorder(self,root):
        if not root:
            return
        self.res.append(root.val)
        self.preorder(root.left)
        self.preorder(root.right)

中序遍历

    def inorder(self,root):
        if not root:
            return
        self.inorder(root.left)
        self.res.append(root.val)
        self.inorder(root.right)

后续遍历

    def postorder(self, root):
        if not root:
            return
        self.postorder(root.left)
        self.postorder(root.right)
        self.res.append(root.val)

代码的完整实现

class Solution:
    res=[]
    def threeOrders(self, root):
        result = []
        self.preorder(root)
        result.append(self.res[:])
        self.res.clear()
        self.inorder(root)
        result.append(self.res[:])
        self.res.clear()
        self.postorder(root)
        result.append(self.res[:])
        self.res.clear()
        return result
        
    def postorder(self, root):
        if not root:
            return
        self.postorder(root.left)
        self.postorder(root.right)
        self.res.append(root.val)

    def preorder(self,root):
        if not root:
            return
        self.res.append(root.val)
        self.preorder(root.left)
        self.preorder(root.right)

    def inorder(self,root):
        if not root:
            return
        self.inorder(root.left)
        self.res.append(root.val)
        self.inorder(root.right)

非递归

同时我们也可以采用非递归的方式来实现，在实现的过程中我们需要引入一个新的数据结构栈。我们以中序遍历为例来看一下执行过程。

image-20210925193225359

image-20210925193244042

image-20210925193259423

下面我们来看一下代码如何实现。

from pyarabic.stack import Stack
def inorder(root):
    res=[]
    stack=Stack()
    while root or stack:
        while root:
            stack.push(root)
            root=root.left

        root=stack.pop()
        res.append(root.val)
        root=root.right

    return res

同理，先序遍历和后序遍历也可以使用非递归的方式实现。

下面，我们给出采用非递归的方式来实现二叉树的三种遍历的代码。

class Solution:

    def threeOrders(self, root):
        result = []
        result.append(self.preorder(root))
        result.append(self.inorder(root))
        result.append(self.postorder(root))
        return result


    def postorder(self, root):
        res = []
        if not root:
            return res

        stack = []
        prev = None

        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if not root.right or root.right == prev:
                ##root.right == prev 用来判断右孩子是否已经访问过了
                res.append(root.val)
                prev = root
                root = None
            else:
                stack.append(root)
                root = root.right
        return res


    def preorder(self, root):
        res = []
        if not root:
            return res

        stack = []
        while stack or root:
            while root:
                res.append(root.val)
                stack.append(root)
                root=root.left

            root = stack.pop()
            root = root.right

        return res

    def inorder(self, root):
        res = []
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left

            root = stack.pop()
            res.append(root.val)
            root = root.right

        return res

二叉树的层序遍历

问题描述：

102. 二叉树的层序遍历

给你一颗二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果：[ [3],[9,20],[15,7]]

分析问题

在开始之前，我们这里先来回顾一下什么是BFS（广度优先搜索）和DFS（深度优先搜索）。

  1. BFS：广度优先搜索是从图中一个未访问的顶点 V 开始，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点，一层层的搜索下去。
  2. DFS：深度优先搜索是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

下面我们来看一下通过BFS和DFS来对二叉树进行遍历。

WeChat3ea3418e74030a4d8b3bcd0012d75e01

WeChatb77686d30c02eb9e40fbdbb3a5cb1e53

WechatIMG72

WechatIMG73

WechatIMG74

WechatIMG75

WechatIMG76

其代码实现如下所示。

DFS遍历：

def dfs(root):
    if not root:
        return
    dfs(root.left)
    dfs(root.right)

BFS遍历：

def bfs(root):
    res = []
    if root: 
       queue = [root]
       while queue:
           node=queue.pop(0)
           res.append(node.val)
           if node.left:
               queue.append(node.left)
           if node.right:
               queue.append(node.right)
    
    return res

回过头来，我们来看一下题目，题目要求是按照层序遍历二叉树。那什么是层序遍历呢，简单来说，就是将二叉树分层，然后对每一层按照从左到右的顺序进行遍历。

image-20210927160354887

看到这里，你有没有发现它和BFS的遍历顺序是一样的。我们可以直接使用BFS算法得出层序遍历的结果。这里需要注意一下，层序遍历和BFS遍历输出的结果是有点区别的。层序遍历要求我们需要区分每一层，即输出一个二维数组。而BFS遍历输出的结果是一维数组，是没办法区分是哪一层的，所以，我们需要对BFS代码稍微修改一下。

def bfs(root):
    if not root:
        return []
    res = []
    queue = []
    queue.append(root)
    while queue:
        #该层的节点数量
        size = len(queue)
        tmp = []
        #遍历把该层元素全部输出
        while size:
            node = queue.pop(0)
            tmp.append(node.val)
            size = size - 1
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(tmp)
    return res

复杂度分析。

  1. 时间复杂度：二叉树中每个结点进队和出队各一次，所以时间复杂度为O(n)。
  2. 空间复杂度：队列中的元素不会超过n个，所以空间复杂度是O(n)。

按之字型顺序打印二叉树

LeetCode 剑指 Offer 32 - III. 从上到下打印二叉树 III

问题描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）。

要求：空间复杂度是O(n)，时间复杂度是O(n)。

例如：给定的二叉树是 {1,2,3,#,#,4,5}

image-20211002110812938

该二叉树之字形层序遍历的结果是[[1]，[3,2]，[4,5]]。

如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。

分析问题

根据题目要求，我们可以得出。

  1. 二叉树是从上到下按层进行输出的。
  2. 奇数层是按照从左到右打印，偶数层是按照从右到左打印

image-20211002112625418

因为题目要求是按层进行遍历，所以我们可以知道是采用层序遍历的算法，不过这里和层序遍历有一点不同的是，对应偶数层，我们要逆序输出，即从右到左打印，所以我们需要引入一个双端队列数据结构，利用它两端都可以添加元素的特性，对奇数层和偶数层进行不同的处理。

  • 奇数层：添加到队列的尾部
  • 偶数层：添加到队列的头部

对于元素 [1，2，3]，如果从尾部添加，则遍历完成时，队列中元素的顺序是 [1, 2, 3] ，输出后是正序的。如果从头部添加，则遍历完成时，队列中元素的顺序是 [3, 2, 1]，输出后是逆序的，从而解决问题。最后，我们来看一下代码的实现。

import collections
def levelOrder(root):
    #如果根节点为空，直接返回空值
    if not root:
        return []
    res = []
    deque = collections.deque([root])
    #队列不为空时
    while deque:
        #双端队列，保存遍历的元素
        tmp = collections.deque()
        #遍历该层元素
        for _ in range(len(deque)):
            node = deque.popleft()
            #偶数层，从前边插入，即队头
            if len(res) % 2:
                tmp.appendleft(node.val)
            else:
                #奇数层，从后边插入，即队尾
                tmp.append(node.val)
            #node的左右孩子入队
            if node.left: 
                deque.append(node.left)
            if node.right: 
                deque.append(node.right)
        #添加到结果列表中        
        res.append(list(tmp))
    return res

该算法的时间复杂度和空间复杂度都是O(N)。

其实我们也可以不使用双端队列，我们可以直接使用列表来实现。如果是奇数层，我们直接添加到结果中，如果是偶数层，我们把列表逆置，然后再加入结果。

def levelOrder(root):
    if not root:
        return []
    res = []
    queue = collections.deque()
    queue.append(root)
    while queue:
        tmp = []
        for _ in range(len(queue)):
            node = queue.popleft()
            tmp.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        if len(res) % 2==0:
            #偶数层,逆序添加
            res.append(tmp[::-1])
        else:
            #奇数层
            res.append(tmp)
    return res

该算法的时间复杂度和空间复杂度都是O(N)。

重建二叉树

LeetCode剑指 Offer 07. 重建二叉树

问题描述

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例：

输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

输出：[3,9,20,null,null,15,7]

image-20211004192454984

分析问题

由于先序遍历是先遍历根节点，然后递归遍历左子树、右子树，而中序遍历是先递归遍历左子树，然后遍历根节点，最后递归遍历右子树。

我们可以知道先序遍历的第一个元素是树的根节点root。由于先序遍历和中序遍历的结果中都不含重复的数字，所以我们可以查找root在中序遍历中的索引，然后将中序遍历结果划分为**[左子树 | 根节点 | 右子树]，然后我们根据中序遍历中左子树和右子树的节点数量，将先序遍历结果划分为[根节点 | 左子树 | 右子树]。这样，我们就可以确定出根结点、左子树根节点、右子树根节点**的位置，然后我们再递归的进行求解。

image-20211004203954730

下面我们来看一下代码实现。

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, vin):
        # write code here
        dic={}
        #为了提升查找效率，将中序遍历里的值和索引放入字典中
        for i in range(len(vin)):
            dic[vin[i]] = i
        #开始时，根节点在先序遍历的索引为0，子树的左边界为0，右边界为len(inorder) - 1
        return self.recur(0, 0, len(vin) - 1,pre,dic)

    """
    root:根节点在先序遍历中的索引位置
    left:子树在中序遍历中的左边界
    right:子树在中序遍历中的右边界
    """
    def recur(self,root, left, right,preorder,dic):
        if left > right:
            return  # 递归终止
        node = TreeNode(preorder[root])  # 建立根节点
        #找出根节点在中序遍历的索引位置，将先序遍历划分为[根节点|左子树|右子树]
        i = dic[preorder[root]]
        #递归遍历左子树，左子树的根节点在root的下一个位置，即root+1
        node.left = self.recur(root + 1, left, i - 1,preorder, dic)
        #递归遍历右子树，左子树的长度为i-left,
        #所以右子树的根节点在先序遍历的位置为i-left+root+1
        node.right = self.recur(i - left + root + 1, i + 1, right, preorder,dic)
        return node  # 回溯返回根节点

##二叉树的右视图

LeetCode 199. 二叉树的右视图

问题描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例：

输入：[1,2,3,null,5,null,4]

输出：[1,3,4]

image-20211011161352153

分析问题

广度优先搜索

我们从右边观察一个二叉树，我们能看到的节点是二叉树每一层上的最右边的节点。所以我们可以对二叉树进行层次遍历，对于二叉树的每层来说，最右边的节点一定是最后遍历到的。

二叉树的层次遍历是采用广度优先搜索实现的。在执行广度优先搜索时，我们对每一层都从左到右访问。因此，只保留每一层最后访问的节点，我们就可以在遍历完整棵树后得到每层的最右的结点。

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        #key 为层数 value为节点值
        rightNode = dict()
        #代表二叉树的深度
        max_depth = -1
        queue = [(root, 0)]
        while queue:
            node, depth = queue.pop(0)
            #记录二叉树的最大深度
            max_depth = max(max_depth, depth)

            #由于每一层中，最后访问的节点是最右边的节点，
            #所以我们进行不断的更新就好
            rightNode[depth] = node.val

            if node.left:
                #放入左节点
                queue.append((node.left, depth + 1))
            if node.right:
                #放入右节点
                queue.append((node.right, depth + 1))
                
        return [rightNode[depth] for depth in range(max_depth + 1)]

算法的时间复杂度是O(n)。每个元素进出队列一次，所以时间复杂度是O(n)。

算法的空间复杂度是O(n)。每个元素进队列一次，所以队列的长度不会超过n，所以空间复杂度是O(n)。

深度优先搜索

其实我们也可以使用深度优先搜索来求解。在搜索的过程中，我们总是先访问右子树。那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。所以，在访问到树的每一层时，我们存储该层的第一个节点，等遍历完整棵树后，就可以得到最终的结果数组。

class Solution:
    def rightSideView(self, root):
        if not root:
            return []
        #key 为层数 value为节点值
        rightNode = dict()
        #代表二叉树的深度
        max_depth = -1
        stack = [(root, 0)]
        while stack:

            node, depth = stack.pop()
            #记录二叉树的最大深度
            max_depth = max(max_depth, depth)

            #如果不存在，才加入
            #只保存没一层第一个结点
            if not rightNode.__contains__(depth):
                rightNode[depth]=node.val

            
            #栈先入后出，所以先出栈右节点
            
            if node.left:
                #放入左节点
                stack.append((node.left, depth + 1))
            if node.right:
                #放入右节点
                stack.append((node.right, depth + 1))

        return [rightNode[depth] for depth in range(max_depth + 1)]

该算法的时间复杂度和空间复杂度都是O(n)。

二叉树的最大深度

LeetCode 104. 二叉树的最大深度

问题描述

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

示例：

输入：给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

输出：3

解释：二叉树的最大深度是 3

分析问题

对二叉树进行遍历，一般有两种方式，即深度优先搜索（DFS）和广度优先搜索（BFS）。所以求解这个问题，我们也可以有两种方式。

深度优先搜索

二叉树的最大深度等于根节点的左子树的深度和右子树的深度的最大值+1，即 max(maxDepth(root.left), maxDepth(root.right))+1。所以，我们可以采用递归的方式来求解。

image-20211012111355601

下面我们来看一下代码实现。

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

该算法的时间复杂度和空间复杂度都是O(N)。

广度优先搜索

我们也可以通过广度优先搜索来实现，每遍历树的一层的时候，我们就使计数器 +1，等遍历结束后，就得到了树的最大深度。

image-20211012112457866

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0
        queue = []
        #根节点入队
        queue.append(root)
        res=0
        while queue:
            #队列长度
            m=len(queue)
            #遍历该层元素
            for i in range(m):
                node=queue.pop(0)
                if node.left: 
                    queue.append(node.left)
                if node.right: 
                    queue.append(node.right)
            #遍历完一层，计算器+1        
            res = res + 1
        return res

该算法的时间复杂度和空间复杂度都是O(N)。

判断是否是平衡二叉树

LeetCode 110. 平衡二叉树

问题描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。

平衡二叉树（Balanced Binary Tree）：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

示例：

输入：给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

输出：true

分析问题

平衡二叉树是指二叉树的每个节点的左右子树的高度差的绝对值不超过1。根据定义，一颗二叉树是平衡二叉树，当且仅当它的所有子树也是平衡二叉树，所以，我们可以使用递归的方式来求解，我们根据递归的顺序不同，可以分为自顶向下和自底向上两种方式。

自顶向下方式（先序遍历+判断）

首先我们定义一个函数height，用来计算二叉树中任意一个节点的高度。然后通过先序遍历二叉树，对于当前遍历到的节点，我们首先计算其左子树和右子树的高度，然后判断其左右子树的高度差是否小于1，如果小于1，代表以该节点为根节点的二叉树是平衡二叉树，然后再分别递归地遍历左右节点，并判断左子树和右子树是否平衡。这是一个自顶向下的过程。如果所有子树都平衡，代表该树是一颗平衡二叉树。

image-20211013151622054

image-20211013151715907

image-20211013151748977

我们来看一下代码实现。

class Solution:
    def IsBalanced_Solution(self, pRoot):
        #求二叉树的高度
        def height(root):
            if not root:
                return 0
            return max(height(root.left), height(root.right)) + 1
        #如果数为空，代表是平衡二叉树，直接返回
        if not pRoot:
            return True
        #左子树的高度
        leftheight=height(pRoot.left)
        #右子树的高度
        rightheight=height(pRoot.right)
        #代表以该节点为根节点的二叉树是平衡的
        if abs(leftheight-rightheight) <=1:
            #再递归判断其左右子树是否是平衡的
            return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
        return False

自底向上的递归

在上面的算法中，我们可以发现对于同一个节点，函数height会被重复调用，导致执行效率不高，如果采用自底向上的解法，对于每个节点，函数height只会被调用一次。

自底向上的递归是指，我们对二叉树进行后序遍历，对于当前遍历到的节点，我们先递归的去判断其左、右子树是否是平衡的，然后再判断以当前节点为根的二叉树是否是平衡的。如果一棵子树是平衡的，则返回其高度，否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定是不平衡。

image-20211013154256638

image-20211013154539777

image-20211013154501120

下面我们来看一下代码实现。

class Solution:
    def IsBalanced_Solution(self, pRoot):
        #递归的求树的高度
        def height(root):
            if not root:
                return 0
            #左子树的高度
            left_height= height(root.left)
            #右子树的高度
            right_height = height(root.right)

            #子树的高度为-1，代表子树不是平衡二叉树，那么该树也不是平衡二叉树，返回-1
            #abs(leftHeight - rightHeight) > 1 代表左右子树的高度差大于1，表示该树是不平衡的，返回-1
            if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
                return -1
            else:
                #否则，返回树的高度
                return max(left_height, right_height) + 1

        #如果树的高度不是-1，代表该树是平衡二叉树
        return height(pRoot) >= 0

该算法的时间复杂度是O(N)，空间复杂度也是O(N)。

由于篇幅长度限制，只能放这么多了，全文在以下链接中：

全文链接

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
二叉树 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入