代码随想录算法训练营第十七天| 110. 平衡二叉树、257.二叉树的所有路径、404. 左叶子之和

代码随想录算法训练营第十七天| 110. 平衡二叉树、257.二叉树的所有路径、404. 左叶子之和

高度VS深度

根结点的高度就是二叉树的最大深度，因此求树深度问题可以转换成求根结点高度的问题，采用后序遍历会好一点，因此在使用递归求解高度时要满足左右根的顺序，先求左边子树高度，再求右边子树高度，最后再通过比较左右子树的高度最大值+1就可以得到当前结点的高度。

题目

110.平衡二叉树

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

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        return False if self.getHeight(root) == -1 else True

    def getHeight(self, root):
        if not root: return 0
        leftHeight = self.getHeight(root.left)
        rightHeight = self.getHeight(root.right)
        return -1 if abs(leftHeight-rightHeight) > 1 or leftHeight == -1 or rightHeight == -1 else 1+max(leftHeight, rightHeight)

回溯思路

递归思路就是从上往下一直遍历，回溯就是在我们发现问题的时候想要退出的时候再重新开始，因此可以把这个递归回溯的过程想成压栈然后弹出。

题目

257.二叉树的所有路径

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

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

# 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]) -> List[str]:
        res = []
        path = []
        if not root: return res
        self.allPathSearch(root, path, res)
        return res

    def allPathSearch(self, root, path, res):
        path.append(root.val)
        if not root.left and not root.right:
            subPath = '->'.join(map(str, path))
            res.append(subPath)
            return
        if root.left:
            self.allPathSearch(root.left, path, res)
            path.pop()
        if root.right:
            self.allPathSearch(root.right, path, res)
            path.pop()

题目

404.左叶子之和

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

# 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
from collections import deque
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        # 递归
        if not root: return 0
        sum_ = 0
        if root.left and not root.left.left and not root.left.right:
            sum_ = root.left.val
        return sum_ + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

        # 非递归
        # sum_ = 0
        # q_ = deque()
        # q_.append(root)
        # while q_:
        #     for _ in range(len(q_)):
        #         node = q_.popleft()
        #         if node.left:
        #             q_.append(node.left)
        #             if not node.left.left and not node.left.right:
        #                 sum_ += node.left.val
        #         if node.right:
        #             q_.append(node.right)
        # return sum_