神奇cpp

这个屌丝很懒，什么也没留下！

热门标签

LeetCode Hot100 ---- 二叉树专题_leetcode hot 树

作者：神奇cpp | 2024-07-05 01:55:00

踩

leetcode hot 树

基础知识：3种traversal

236, 297, 102, 314, 98

树

力扣102：二叉搜索树的层次遍历

力扣105：从前序和中序重构二叉树

力扣108：将有序数组转化为二叉搜索树

力扣110：平衡二叉树

力扣113：路径总和

力扣124：二叉树的最大路径和

力扣1325：删除给定值的叶子节点

力扣144：二叉树的前序遍历（非递归）

力扣145：二叉树的后续遍历（非递归）

力扣199：二叉树的右视图

力扣208：实现Trie前缀树

力扣222：完全二叉树的节点数

力扣226：翻转二叉树

力扣236：二叉树的最近公共祖先

力扣257：二叉树的所有路径

力扣297：二叉树的序列化和反序列化

力扣450：删除二叉树中的节点

力扣543：二叉树的直径长度

力扣617：合并二叉树

力扣662：二叉树的最大宽度

力扣687：最长同值路径

力扣94：二叉树中序遍历（非递归）

力扣958：二叉树的完全性检验

力扣98：验证二叉搜索树

力扣99：恢复二叉搜索树

重建二叉树

Z字形层次遍历

知识点

掌握二叉树递归与非递归遍历
理解 DFS 前序遍历与分治法
理解 BFS 层次遍历

二叉树遍历

前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树
中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树
后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点

注意点

以根访问顺序决定是什么遍历
左子树都是优先右子树

递归模板

递归实现二叉树遍历非常简单，不同顺序区别仅在于访问父结点顺序


# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def preorder(root):
            if not root:
                return
            res.append(root.val)
            preorder(root.left)
            preorder(root.right)
        
        res = []
        preorder(root)
        return res
 
 
 
def preorder_rec(root):
    if root is None:
        return
    visit(root)
    preorder_rec(root.left)
    preorder_rec(root.right)
    return
 
def inorder_rec(root):
    if root is None:
        return
    inorder_rec(root.left)
    visit(root)
    inorder_rec(root.right)
    return
 
def postorder_rec(root):
    if root is None:
        return
    postorder_rec(root.left)
    postorder_rec(root.right)
    visit(root)
    return

前序非递归

本质上是图的DFS的一个特例，因此可以用栈来实现


class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        res, stack = [], [root] # 利用栈进行临时存储
        while stack:
            node = stack.pop() # 取出一个节点，表示开始访问以该节点为根的子树
            res.append(node.val) # 首先访问该节点（先序），之后顺序入栈右子树，左子树
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res
'运行

中序非递归

中序遍历的思想是：
1.若节点还有左子树，就要把左子树访问完；
2.没有左子树可以访问时，访问该节点，并尝试访问右子树


class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack, inorder = [], []
        node = root
        while len(stack) > 0 or node is not None:
            if node is not None:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                inorder.append(node.val)
                node = node.right
        return inorder

后序非递归

后序遍历（迭代法）

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root):
        
        preorder = []
        if root is None:
            return preorder
        
        s = [root]
        while len(s) > 0:
            node = s.pop()
            preorder.append(node.val)
            if node.left is not None:
                s.append(node.left)
            if node.right is not None:
                s.append(node.right)
        
        return preorder[::-1]

后续遍历的主要特点是：遍历左分支的左右根节点，再把左分支的主干节点逐个返回。

分治法应用

先分别处理局部，再合并结果

适用场景

快速排序
归并排序
二叉树相关问题

分治法模板

递归返回条件
分段处理
合并结果

104. 二叉树的最大深度

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


 class Solution:
     def maxDepth(self, root: TreeNode) -> int:
         if not root:
             return 0
         return 1 + max([self.maxDepth(root.left), self.maxDepth(root.right)])
'运行

思路 2：层序遍历


class Solution:
    def maxDepth(self, root: TreeNode) -> List[List[int]]:
        
        depth = 0
        if root is None:
            return depth
        
        bfs = collections.deque([root])
        
        while len(bfs) > 0:
            depth += 1
            level_size = len(bfs)
            for _ in range(level_size):
                node = bfs.popleft()
                if node.left is not None:
                    bfs.append(node.left)
                if node.right is not None:
                    bfs.append(node.right)
        
        return depth

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

思路：

得到中序遍历的结果；
判断中序遍历是否单调递增。


 class Solution:
     def isValidBST(self, root: TreeNode) -> bool:
         def get_mfs(root):
             if not root:
                 return []
             return get_mfs(root.left) +[root.val] + get_mfs(root.right)
 
         res = get_mfs(root)    
         if len(res) <= 1:
             return True
         for i in range(1,len(res)):
             if res[i] <= res[i-1]:
                 return False
         return True

分治法: 一个二叉树为合法的二叉搜索树当且仅当左右子树为合法二叉搜索树且根结点值大于右子树最小值小于左子树最大值。


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root):
        if root is None: 
            return True
        
        def valid_min_max(node):
            
            isValid = True
            if node.left is not None:
                l_isValid, l_min, l_max = valid_min_max(node.left)
                isValid = isValid and node.val > l_max
            else:
                l_isValid, l_min = True, node.val
 
            if node.right is not None:
                r_isValid, r_min, r_max = valid_min_max(node.right)
                isValid = isValid and node.val < r_min
            else:
                r_isValid, r_max = True, node.val
 
            return l_isValid and r_isValid and isValid, l_min, r_max
        
        return valid_min_max(root)[0]


class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        
        if root is None:
            return True
        
        s = [(root, float('-inf'), float('inf'))]
        while len(s) > 0:
            node, low, up = s.pop()
            if node.left is not None:
                if node.left.val <= low or node.left.val >= node.val:
                    return False
                s.append((node.left, low, node.val))
            if node.right is not None:
                if node.right.val <= node.val or node.right.val >= up:
                    return False
                s.append((node.right, node.val, up))
        return True
'运行

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

解题思路：

左子树+右子树+1（父节点）代表路径长度，递归计算长度，用全局res记录最长路径。最终返回res-1（直径用边的数目表示）


class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.ans = 1
        def depth(node):
            # 访问到空节点了，返回0
            if not node:
                return 0
            # 左儿子为根的子树的深度
            L = depth(node.left)
            # 右儿子为根的子树的深度
            R = depth(node.right)
            # 计算d_node即L+R+1 并更新ans
            self.ans = max(self.ans, L + R + 1)
            # 返回该节点为根的子树的深度
            return max(L, R) + 1
 
        depth(root)
        return self.ans - 1

102. 二叉树的层序遍历

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

示例：

返回其层序遍历结果：


 [
   [3],
   [9,20],
   [15,7]
 ]

思路：二叉树的题目很多适合用递归，因为二叉树本身就是由相同的节点结构组成。而此题用迭代实现更直观。


# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        #跟结点入queue
        queue = [root]
        res = []
        while queue:
            res.append([node.val for node in queue])
            #存储当前层的孩子节点列表
            ll = []
            #对当前层的每个节点遍历
            for node in queue:
                #如果左子节点存在，入队列
                if node.left:
                    ll.append(node.left)
                #如果右子节点存在，入队列
                if node.right:
                    ll.append(node.right)
            #后把queue更新成下一层的结点，继续遍历下一层
            queue = ll
        return res
'运行

对于题目199，右视图即每层最右边的值，因此只需要做一个非常简单的小变化，即返回的列表只需要对每一层的列表的最后一个元素入结果列表就可以了


#只需要对该层最后一个元素入列表
res.append([node.val for node in queue][-1])


 
# 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 rightSideView(self, root: TreeNode) -> List[int]:
        if not root: return []
        #跟结点入queue
        queue = [root]
        res = []
        while queue:
            #只需要对该层最后一个元素入列表
            res.append([node.val for node in queue][-1])
            #存储当前层的孩子节点列表
            ll = []
            #对当前层的每个节点遍历
            for node in queue:
                #如果左子节点存在，入队列
                if node.left:
                    ll.append(node.left)
                #如果右子节点存在，入队列
                if node.right:
                    ll.append(node.right)
            #后把queue更新成下一层的结点，继续遍历下一层
            queue = ll
        return res

437. 路径总和 III

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

基本思路：先回溯得到以根节点为起点(一定包含根节点)的路径和满足要求的总数。再深度优先搜索，即根节点路径数目+左节点路径数目+右节点路径数目


class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        def backtrace(root, sum):
            res = 0
            if not root:
                return res
            if sum == root.val:
                res += 1
            if root.left:
                res += backtrace(root.left, sum - root.val)
            if root.right:
                res += backtrace(root.right, sum - root.val)
            return res
        # 返回路径和等于数值的路径数
        def DFS(root):
            if not root:
                return 0
            root_count = backtrace(root, targetSum)
 
            left_root = DFS(root.left)
            right_root = DFS(root.right)
            return left_root+right_root+root_count
            
        return DFS(root)

617. 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:


输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
注意: 合并必须从两个树的根节点开始。

思路：经典左右递归


class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t2:
            return t1
        elif not t1:
            return t2
        else:
            t3 = TreeNode()
            t3.val = t1.val + t2.val
            t3.left = self.mergeTrees(t1.left,t2.left)
            t3.right = self.mergeTrees(t1.right,t2.right)
            return t3

226. 翻转二叉树

左右翻转一棵二叉树。

思路：经典左右递归


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

105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树, 树中没有重复的元素。

例如：


前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回：
    3
   / \
  9  20
    /  \
   15   7

思路：前序遍历[根节点，左子树，右子树]，中序遍历[左子树，根节点，右子树]，显然前序遍历第一个为根节点，根据根节点在中序遍历中定位左右子树的中序遍历，同时可知左右子树的元素数量，由此在前序遍历中找到左右子树的前序遍历。由此递归。


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return
        root = TreeNode()
        root.val = preorder[0]
        index = inorder.index(root.val)
        root.left = self.buildTree(preorder[1:index+1],inorder[:index])
        root.right = self.buildTree(preorder[index+1:],inorder[index+1:])
        return root

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

思路：

某节点是公共祖先有两种情况：

该节点为指定节点中的一个，且子树中存在另一个节点。
该节点不是指定节点，但其左右子树均存在指定节点。


class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return
        if root==q or root==p:
            return root # 可能为情况1，也可能是情况1中的子树
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if left and right:
            return root # 情况2
        if not left:
            return right
        if not right:
            return left

538. 把二叉搜索树转换为累加树

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于node.val的值之和。

思路：

本题中要求我们将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。这样我们只需要反序中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。

其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，大家是不是感觉这就是送分题了。

为什么变成数组就是送分题了呢，因为数组大家都知道怎么遍历啊，从后向前，挨个累加就完事了，这换成了二叉搜索树，看起来就别扭了一些是不是。

那么知道如何遍历这个二叉树，也就迎刃而解了，从树中可以看出累加的顺讯是右中左，所以我们需要中序遍历反过来遍历这个二叉树，然后顺序累加就可以了。


class Solution:
    def __init__(self):
        self.accum = 0
 
    def convertBST(self, root: TreeNode) -> TreeNode:
        if not root:
            return 
        # 接下来逆中序遍历root
        self.convertBST(root.right) # 1. 遍历右子树
        root.val += self.accum # 2. 遍历当前结点
        self.accum = root.val 
        self.convertBST(root.left) # 3. 遍历左子树
        return root
'运行

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

递归思路：


class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def is_sym(a,b):
            if not a and not b:
                return True
            elif not a or not b:
                return False
            if a.val != b.val:
                return False
            return is_sym(a.left,b.right) and is_sym(a.right,b.left)
        if not root:
            return True
        return is_sym(root.left,root.right)

迭代思路，一层一层遍历，每层查看是否对称：


class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        layer = [root]
        while layer:
            vals = [root.val if root else None for root in layer ]
            if vals!=vals[::-1]:
                return False
            layer = [(root.left, root.right) for root in layer if root]
            layer = [i for tpl in layer for i in tpl]
        return True

297. 二叉树的序列化与反序列化

将二叉树转化为字符串，并且可以将字符串再转化为原始的二叉树。

思路：

序列化的就是把数据结构转为字符串，可以使用DFS的方式，二叉树DFS的方法就是对每个节点，都先处理左子节点，再处理右子节点。

先了解，二叉树序列化其实是按照某种遍历方式，结果以某种格式保存为字符串。
采用 dfs 的方法（同样可以使用 bfs），按照先序遍历的访问方式，序列化二叉树。这里使用先序遍历的方法，同样是方便反序列化时能够快速定位到根节点。因为先序遍历的访问顺序为：先访问根节点，然后遍历左子树，最后遍历右节点。
进行序列化的时候，当遇到 None 时，需要进行标识，这样在反序列化的时候才能够分辨此处为 None，是空树。
反序列化，按照先序遍历的访问规则，分割前面序列化后的字符串，按照从左到右的顺序遍历：

当元素为 null 时，表示是空树；
否则先解析左子树，再解析右子树。

我们使用递归的时候，只需要关注单个节点，剩下就交给递归实现。使用先序遍历的是因为：先序遍历的访问顺序是先访问根节点，然后遍历左子树，最后遍历右子树。这样在我们首先反序列化的时候能够直接定位到根节点。

这里有个需要注意的地方，当遇到 null 节点的时候，要进行标识。这样在反序列化的时候才能够分辨出这里是 null 节点。


class Codec:
    def serialize(self, root):
        vals = []
 
        def dfs(node):
            if node:
                vals.append(str(node.val))
                dfs(node.left)
                dfs(node.right)
            else:
                vals.append("#")
 
        dfs(root)
        s = " ".join(vals)
        return s
 
    def deserialize(self, data):
 
        def redfs():
            if vals:
                val = vals.pop(0)
            else:
                return
            if val == "#":
                return None
            node = TreeNode(int(val))
            node.left = redfs()
            node.right = redfs()
            return node
 
        vals = data.split(" ")
        return redfs()

124. 二叉树中的最大路径和

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其最大路径和。

思路：

递归，对每个节点，最大值有四种情况：

仅该节点（比如左右子树都是负数）
该节点加左子树单链最大值
该节点加右子树单链的最大值
该节点加左右子树单链的最大值


class Solution:
    def __init__(self):
        self.maxSum = float("-inf")
 
    def maxPathSum(self, root):
        def maxGain(node):
            if not node:
                return 0
 
            # 递归计算左右子节点的最大贡献值
            # 只有在最大贡献值大于 0 时，才会选取对应子节点
            leftGain = max(maxGain(node.left), 0)
            rightGain = max(maxGain(node.right), 0)
            
            # 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
            priceNewpath = node.val + leftGain + rightGain
            
            # 更新答案
            self.maxSum = max(self.maxSum, priceNewpath)
        
            # 返回节点的最大贡献值
            return node.val + max(leftGain, rightGain)
   
        maxGain(root)
        return self.maxSum
'运行

balanced-binary-tree

给定一个二叉树，判断它是否是高度平衡的二叉树。

思路 1：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1


class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
 
        def depth(root):
            
            if root is None:
                return 0, True
            
            dl, bl = depth(root.left)
            dr, br = depth(root.right)
            
            return max(dl, dr) + 1, bl and br and abs(dl - dr) < 2
        
        _, out = depth(root)
        
        return out
'运行

insert-into-a-binary-search-tree

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。

思路：如果只是为了完成任务则找到最后一个叶子节点满足插入条件即可。


class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        
        if root is None:
            return TreeNode(val)
        
        node = root
        while True:
            if val > node.val:
                if node.right is None:
                    node.right = TreeNode(val)
                    return root
                else:
                    node = node.right
            else:
                if node.left is None:
                    node.left = TreeNode(val)
                    return root
                else:
                    node = node.left

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。


class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        
        if root is None:
            return TreeNode(val)
        
        if val > root.val:
            root.right = self.insertIntoBST(root.right, val)
        else:
            root.left = self.insertIntoBST(root.left, val)
        
        return root

练习

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/788846