LeetCodeCampsDay15二叉树part03

涉及树的高度/深度求解，以及平衡二叉树的判断，完全二叉树求节点个数；
根节点到任意节点的路径/深度求解

平衡二叉树

https://leetcode.cn/problems/balanced-binary-tree/

给定一个二叉树，判断它是否是平衡二叉树

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

后序递归思路

这里强调一波概念：

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

但leetcode中强调的深度和高度很明显是按照节点来计算的，如图：

如何判断一个树是不是平衡二叉树？—判断它的左树和右树的高度是否差大于1

使用递归+后序遍历方法

输入节点；输出高度（或者-1，表示高度差已经大于1了）
终止条件：节点为空返回0
单层逻辑：分别求左、右子树的高度，判断两者高度差，如果大于1则返回-1；否则返回1+max(左,右)

顺便提一下，在day14写过“求最大深度”，当时也使用后序递归算法；当时仅需要每个节点找到子树的深度，再加一即可

leftDeepth = self.traverse(node.left)
rightDeepth = self.traverse(node.right)
return max(leftDeepth, rightDeepth) + 1

而现在需要求每个节点的子树高度，是同样的代码，因为求最大深度，即**“根节点的高度就是二叉树的最大深度”**

leftHeight = self.getHeight(node.left)
rightHeight = self.getHeight(node.right)
return 1 + max(leftHeight, rightHeight)

但需要添加几个约束条件，比如求了leftH和righH后判断两者是否为-1，如果是，直接提前退出；以及判断两者高度差是否大于1

后序递归代码

时间复杂度O(N)
空间复杂度O(H)

# 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 getHeight(self, node) -> int:
        if not node:
            return 0
        # 分别求左、右子树的高度，如果高度差大于1，则返回-1
        leftHeight = self.getHeight(node.left)
        if leftHeight == -1:
            return -1
        rightHeight = self.getHeight(node.right)
        if rightHeight == -1:
            return -1
        if abs(leftHeight - rightHeight) > 1:
            return -1
        else:
            return 1 + max(leftHeight, rightHeight)

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # 本题目尝试用递归法
        res = self.getHeight(root)
        if res != -1:
            return True
        return False

257. 二叉树的所有路径

https://leetcode.cn/problems/binary-tree-paths/

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

提示：

树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100

思路

已知前序遍历是长这样的

还是按递归的方式写个前序，但终止条件有点儿不同，以往是判断node为空就直接返回，但这题目需要判断“如果当前节点为叶子节点”，就将根到节点的路径保存。所以，还需要有个path列表来记录路径，同时还需要个res列表记录所有从根节点到叶子节点的路径

于是，

递归的输入：node, path, res；输出就是res（用引用的方式输出就好）
终止条件：当前节点无孩子节点，则将当前的path添加到res里
单层逻辑：依然使用前序遍历，但需要添加判断条件，仅当left/right不为空时才能执行递归；而且递归后，需要将当前节点从path中弹出去
1. 比如[1,2,3,null,5],当找到了path=[1,2,5]后，如果不把[2,5]弹出，下次path会记录成[1,2,5,3]而不是正确答案[1,3]

本题使用递归写简单直接一点儿，用迭代也可以完成

递归代码

时间复杂度O(N)
空间复杂度O(H)

# 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 preOrder(self, node: TreeNode, path: list, res: list):
        # 操作, 必须放最前面（在终止条件前面）
        path.append(node.val)

        # 终止条件
        if not node.left and not node.right:
            # res里已经记录了[1,2,5]，需要将它转成1->2->5
            s = ""
            for i in range(len(path) - 1):
                s += (str(path[i]) + "->")
            s += str(path[-1])
            res.append(s)
        
        # 遍历
        if node.left:
            self.preOrder(node.left, path, res)
            # 回溯只会发生在，当前节点的子节点都被遍历完了
            # 假设现在子节点已经被遍历完，需要进行回溯
            path.pop()
        if node.right:
            self.preOrder(node.right, path, res)
            # 回溯
            path.pop()


    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        # 先用递归实现个前序遍历
        res = list()
        path = list()
        self.preOrder(root, path, res)
        return res

迭代代码

迭代的过程更简单一点儿

时间复杂度O(N)
空间复杂度O(H)

  stack = list()
  path = list()
  res = list()
  stack.append(root)
  path.append(str(root.val))
  while stack:
      node = stack.pop()
# 先把节点从path中弹出
      pathNode = path.pop()
      # 为了实现中、前、后，入栈需要使用中、后、前
      if not node.left and not node.right:
          res.append(pathNode)
      
      if node.right:
          stack.append(node.right)
          # 
          path.append(pathNode + "->" + str(node.right.val))
      
      if node.left:
          stack.append(node.left)
          path.append(pathNode + "->" + str(node.left.val))
  
  return res

思考

day14以及day15中都有求二叉树的高度的题目（实现起来不难），并且有一个求最大深度的题目（但当时是直接用“根节点的高度“），但它规避了求某个节点所在深度的问题

深度的定义：指从根节点到该节点的最长简单路径边的长度

比如[3,9,20,7]，其中7所在深度为3，对应的路径为[3,20,7]长度也为3

那么问题可以变成如何求根节点到任意节点的路径，思路可以和本题很像，这题目的终止条件是“遇到叶子节点”才把路径添加到res；而可以扩展成，遇到“target节点”就把路径添加到res

# 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 binaryTreePaths(self, root: Optional[TreeNode], target: Optional[TreeNode]) -> List[str]:
        stack = list()
        path = list()
        res = list()
        stack.append(root)
        path.append(str(root.val))
        while stack:
            node = stack.pop()
            pathNode = path.pop()
            # 为了实现中、前、后，入栈需要使用中、后、前
            # 这里使用val数值判断，当然可以通过地址判断，从而唯一对应target
            # if node.val == target.val:
            #     res.append(pathNode)
            # 可以使用地址进行唯一的对应
            if node == target:
                res.append(pathNode)
            
            if node.right:
                stack.append(node.right)
                path.append(pathNode + "->" + str(node.right.val))
            
            if node.left:
                stack.append(node.left)
                path.append(pathNode + "->" + str(node.left.val))
        
        return res

so = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
target = TreeNode(5)
root.left.left = target
print(so.binaryTreePaths(root, target))

输入root为[1,2,3,null,5]，target为[5]

输出[‘1->2->5’]，从而得知5的深度为3

404. 左叶子之和

https://leetcode.cn/problems/sum-of-left-leaves/

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1]
输出: 0

提示:

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000

递归思路

这题目要求是求“左子树之和”，如图所示；

可以使用递归的后序遍历

终止条件：if not node: return 0
输入输出：输入为node，输出为int，表示当前节点的左叶子之和
单层递归逻辑：求左子树的左叶子和、右子树的左叶子之和，再将两者相加，得到了当前节点的左叶子之和（这也是使用后序遍历的原因）

但有个不同点，如何判断当前节点是父节点的左叶子；

可以当父节点是当前节点时，判断node.left.left和node.left.right是否为空，判断当前的左子节点是否为空，如果其左子节点是叶子，则当前节点的左子树之和就是node.left.val

递归代码

时间复杂度O(N)
空间复杂度O(H)

# 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 postOrder(self, node: TreeNode) -> int:
        # 终止条件
        # 如果当前节点为空，则返回0
        if not node:
            return 0
        # 终止条件二，找到了叶子节点，返回零，因为它的左右子树为空(Optional，不写这个终止条件也行，无非是多递归一层)
        if not node.left and not node.right:
            return 0
        # 需要在当前节点，判断，它的左子节点是否为空，如果不为空，则判断它左子节点是否为叶子节点
        # 左子树
        sumOfLeft = self.postOrder(node.left)
        # 左子树的特殊情况，即“左叶子节点”，此时才能将 sumOfLeft 设置为 node.left.val
        if node.left:
            if not node.left.left and not node.left.right:
                sumOfLeft = node.left.val
        # 右
        sumOfRight = self.postOrder(node.right)
        # 中，求合
        return sumOfLeft + sumOfRight

    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        # 使用后序遍历，目标是从收集左子树和右子树的“左叶子之和”，再将总和相加
        return self.postOrder(root)

迭代思路

仍然使用后序遍历，注意入栈时，先中、再右、最后左，这样才能让出栈时的顺序为“左、右、中”
迭代的过程看着更简单一点儿
使用前序/中序也可以完成任务，而且这题目对实际顺序不敏感
比如入栈顺序为[中，右，左]、[中，左，右]、[左，中，右]、[右，中，左]、[左，右，中]、[右，左，中]都可以

迭代代码

时间复杂度O(N)
空间复杂度O(H),最坏O(N)，最好O(logN)

def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
    # 使用后序遍历（迭代）
    stack = list()
    if not root:
        return 0
    stack.append(root)
    sumLeftLeaves = 0
    while stack:
        node = stack.pop()
        if node.left and not node.left.left and not node.left.right:
            sumLeftLeaves += node.left.val
        # 注意使用栈时的入栈顺序，先right再left
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return sumLeftLeaves

这题目使用前序也可以，如果使用栈+迭代，最好从while的底层向上读代码来理解实际的输出顺序

def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
    stack = list()
    if not root:
        return 0
    stack.append(root)
    sumLeftLeaves = 0
    while stack:
      	# 前序，后入先出
        node = stack.pop()
        # 保持"右，左，中“入栈，才能得到“中左右”的效果
        # 处理右
        if node.right:
            stack.append(node.right)
        # 处理左
        if node.left:
            stack.append(node.left)
        # 处理中
        if node.left and not node.left.left and not node.left.right:
            sumLeftLeaves += node.left.val
    
    return sumLeftLeaves

222. 完全二叉树的节点个数

https://leetcode.cn/problems/count-complete-tree-nodes/

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

提示：

树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树

**进阶：**遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

普通树处理思路

不管它是什么树，直接用前/中/后/层序遍历处理（递归）就行
递归输入：节点，输出：子树的节点个数
终止条件：节点为空返回0
单层逻辑：求左、右子树节点个数，再计算总和并加一

普通树的递归代码

时间复杂度O(N)
空间复杂度O(H) – 最坏O(N)，最好O(logN)

# 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:
    # 使用递归求解, 尝试后序
    # 返回子树的节点个数, 如果当前普通树处理，时间复杂度为O(N)
    def postOrder(self, node: TreeNode) -> int:
        if not node:
            return 0
        countOfLeft = self.postOrder(node.left)
        countOfRight = self.postOrder(node.right)
        return countOfLeft + countOfRight + 1

    def countNodes(self, root: Optional[TreeNode]) -> int:
        return self.postOrder(root)

普通树的迭代代码

使用前序

def countNodes(self, root: Optional[TreeNode]) -> int:
    # 使用栈+迭代实现
    stack = list()
    if not root:
        return 0
    stack.append(root)
    count = 0
    while stack:
        node = stack.pop()
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
        count += 1
    return count

使用层序

def countNodes(self, root: Optional[TreeNode]) -> int:      
			from collections import deque
      que = deque()
      if not root:
          return 0
      que.append(root)
      count = 0
      while que:
          node = que.popleft()
          count += 1
          if node.right:
              que.append(node.right)
          if node.left:
              que.append(node.left)
          
      return count

完成二叉树思路

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

完全二叉树（一）如图：

完全二叉树（二）如图：

可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。

这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？ —如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树

顺便提一句，如何判断一个树是否为平衡二叉树？----判断左、右子树的高度差，如果高度差大于1则不是

下面这图中“向右遍历的深度为2”指的是，令rightNode = node.right，并且循环rightNode = rightNode.right并count+=1，一路向右，如果出现了“非满二叉树”就出出现深度为2，否则深度一定为3；就像左边一样

通过leftNode一路向左，rightNode一路向右，来判断子树的深度是否一样，是否是满二叉树
之所以能用leftNode一路向左，rightNode一路向右，也是利用了完全二叉树的性质

完全二叉树代码

class Solution:
    def countNum(self, node: TreeNode) -> int:
        if not node:
            return 0
        
        leftNode = node.left
        rightNode = node.right
        # 求左、右子树的深度
        leftDepth = 0
        rightDepth = 0
        # leftNode一路向左
        while leftNode:
            leftNode = leftNode.left
            leftDepth += 1
        # rightNode一路向右
        while rightNode:
            rightNode = rightNode.right
            rightDepth += 1
        # 满二叉树
        if leftDepth == rightDepth:
            # 直接返回总数2^D - 1
            return (2 << leftDepth) - 1
        
        # 单层逻辑
        leftNum = self.countNum(node.left)
        rightNum = self.countNum(node.right)
        return leftNum + rightNum + 1
        
		def countNodes(self, root: Optional[TreeNode]) -> int:
        # 完全二叉树统计
        return self.countNum(root)