Day 18 二叉树：513. 底层左下角, 112|113. 路径总和I II, 106. 中序|后序构造, 105. 前序|中序构造

513. 找树左下角的值

思路
- example
- 迭代，层序遍历bfs ，最后一层第一个节点。
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        que = collections.deque()
        res = -1
        if root:
            que.append(root)
        while que:
            size = len(que)
            for i in range(size):
                node = que.popleft()
                if i == 0:
                    if node.left == None and node.right == None:
                        res = node.val 
                if node.left:
                    que.append(node.left) 
                if node.right:
                    que.append(node.right) 
        return res

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        que = collections.deque()
        res = -1
        if root:
            que.append(root)
        while que:
            size = len(que)
            for i in range(size):
                node = que.popleft()
                if i == 0:
                    res = node.val 
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right) 
        return res

递归，前序（自上而下）, dfs，回溯
- 左下角：
  －叶子：node的children 为空
  - 最下一层最左叶子：利用depth 来判断是否最下一层, 前序遍历保证了第一个更新depth的节点为最左叶子。

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        def traversal(root, depth):
            nonlocal max_depth, res
            if root.left == None and root.right == None:
                if depth > max_depth:
                    max_depth = depth 
                    res = root.val
                    return 
            if root.left:
                depth += 1
                traversal(root.left, depth)
                depth -= 1
            if root.right:
                depth += 1
                traversal(root.right, depth)
                depth -= 1
        max_depth= -float('inf')
        res = -float('inf')
        traversal(root, 1)
        return res

112. 路径总和

思路
- example
- 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
- 递归，前序，回溯
  - 递归函数传递参数pathsum，返回值 True or False，方便提早退出遍历。
  - 也可以维护当前path与targetsumr的差值。
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def traversal(root, pathsum):
            if root.left == None and root.right == None:
                if pathsum == targetSum:
                    return True
                else: 
                    return False
            if root.left: 
                pathsum += root.left.val
                flag = traversal(root.left, pathsum)
                if flag:
                    return True
                pathsum -= root.left.val
            if root.right:
                pathsum += root.right.val
                flag = traversal(root.right, pathsum)
                if flag:
                    return True
                pathsum -= root.right.val
            return False 
        if root == None:
            return False
        return traversal(root, root.val)

回溯框架比较方便

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def traversal(root, pathSum):
            if root.left == None and root.right == None:
                if pathSum == targetSum:
                    return True 
                else:
                    return False 
            if root.left:
                flag = traversal(root.left, pathSum + root.left.val) 
                if flag:
                    return True  
            if root.right:
                flag = traversal(root.right, pathSum + root.right.val)  
                if flag:
                    return True 
            return False 
        if root == None:
            return False  
        return traversal(root, root.val)

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def traverse(root):
            nonlocal pathSum 
            if root.left == None and root.right == None:
                if pathSum == targetSum:
                    return True  
                else:
                    return False  
            if root.left:
                pathSum += root.left.val 
                if traverse(root.left):
                    return True  
                pathSum -= root.left.val 
                # return False  # !!!
            if root.right:
                pathSum += root.right.val 
                if traverse(root.right):
                    return True  
                pathSum -= root.right.val 
            return False  # !!!
        if root == None:
            return False  
        pathSum = root.val 
        return traverse(root)

DFS框架要注意在base case返回值进行“撤销”操作。

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def traversal(root):
            nonlocal pathSum
            if root == None:
                return False 
            pathSum += root.val 
            if root.left == None and root.right == None:
                if pathSum == targetSum:
                    pathSum -= root.val 
                    return True 
                else:
                    pathSum -= root.val # !!!
                    return False 
            valid_left = traversal(root.left)
            if valid_left:
                return True 
            valid_right = traversal(root.right) 
            if valid_right:
                return True 
            pathSum -= root.val
            return False  
        pathSum = 0
        return traversal(root)

递归，后序, 自下而上
- 比较不自然。

TBA

迭代，层序遍历
- 入deque的时候把当前pathsum也加进去。
- 每一层popleft()出来node的时候判断是否叶子节点。若是，则比较pathsum 和 targetsum.

TBA

113. 路径总和 II

思路
- example
- 类似上题，这里要找出所有可行答案。
- 回溯框架
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        def traversal(root, pathsum):
            if root.left == None and root.right == None:
                if pathsum == targetSum:
                    res.append(path[:])
                    return
            if root.left: 
                pathsum += root.left.val
                path.append(root.left.val)
                traversal(root.left, pathsum)
                path.pop()
                pathsum -= root.left.val
            if root.right:
                pathsum += root.right.val
                path.append(root.right.val)
                traversal(root.right, pathsum)
                path.pop()
                pathsum -= root.right.val
        if root == None:
            return []
        res, path = [], [root.val]
        traversal(root, root.val)
        return res

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        def traversal(root, path):
            if root.left == None and root.right == None:
                if sum(path) == targetSum:
                    res.append(path[:])
                    return 
            if root.left: 
                path.append(root.left.val) 
                traversal(root.left, path)
                path.pop()
            if root.right:
                path.append(root.right.val) 
                traversal(root.right, path)
                path.pop() 
        res = []
        if root == None:
            return res 
        path = [root.val]
        traversal(root, path)
        return res

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        def traversal(root, pathSum):
            if root.left == None and root.right == None:
                if pathSum == targetSum:
                    res.append(path[:])
                return 
            if root.left:
                path.append(root.left.val)
                traversal(root.left, pathSum+root.left.val) 
                path.pop()
            if root.right:
                path.append(root.right.val)
                traversal(root.right, pathSum+root.right.val)
                path.pop()  
        if root == None:
            return []
        res = []
        path = [] 
        path.append(root.val) 
        traversal(root, root.val)
        return res

106. 从中序与后序遍历序列构造二叉树

思路
- example
- 树中每个node的值都不同，这样可以用值唯一确定node.
- 递归构造树。找出并建立树的根节点，然后划分inorder和postorder数组，递归构造左子树和右子树，并且链接起来。这里的关键是找出切割位置（根节点），并且划分左子树和右子树对应的两个子数组。
  - 构造树（假设是最基本的三个元素的满树）：先建立根节点。然后处理左节点和右节点前且链接起来。
  - 例子：
    
    inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
    - postorder（左右中）最右边即为根节点
    - inorder(左中右）需要线性扫描找到pivot位置，pivot左边是左子树 [9]，pivot右边是右子树 [15,20,7]
    - postorder左子树取inorder左子树相同size即可 [9]，postorder右子树同理 [15,20,7]。
    - 注意指标的取值范围。
  - 递归函数：参数为当前节点，inorder, postorder。
  - 基本case: 注意有可能左或右子树可能为空，所以要处理[]情况。
  - 返回值：根节点
复杂度. 时间：O(n)?, 空间: O(n)

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # len(inorder) == len(postorder)
        # Base Case
        if postorder == []:
            return None
        val = postorder[-1] # 根节点数值
        root = TreeNode(val) # 建立节点
        # Find pivot in inorder 
        pivot = 0
        for i in range(len(inorder)):
            if inorder[i] == val:
                pivot = i
                break 
        # partition inorder and postorder
        # 左中右
        # 左右中
        inorder_left, inorder_right = inorder[:pivot], inorder[pivot+1:]
        size_left, size_right = len(inorder_left), len(inorder_right)
        postorder_left, postorder_right = postorder[:size_left], postorder[size_left : size_left+size_right]
        # recursive and link
        root.left = self.buildTree(inorder_left, postorder_left)
        root.right = self.buildTree(inorder_right, postorder_right)
        return root

可以“优化”，传递inorder和postorder数组的start,end指标来确定左右子树。

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def traversal(start1, end1, start2, end2): # 1: inorder, 2: postorder 
            if start1 > end1:
                return None 
            root_val = postorder[end2]
            root = TreeNode(root_val) 
            # 分割
            pivot_idx = 0
            while pivot_idx <= end1: 
                if inorder[pivot_idx] == root.val:
                    break 
                pivot_idx += 1
            left_size = pivot_idx - start1
            root.left = traversal(start1, pivot_idx-1, start2, start2+left_size-1)
            root.right = traversal(pivot_idx+1, end1, start2+left_size, end2-1)
            return root 
        n = len(inorder)
        return traversal(0, n-1, 0, n-1)

这个更简洁

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def build(inorder, postorder): 
            n = len(inorder)
            if n == 0:
                return None 
            root = TreeNode(postorder[-1]) 
            val = postorder[-1]
            idx = -1
            for i in range(n):
                if inorder[i] == val:
                    idx = i
                    break 
            root.left = build(inorder[0:idx], postorder[0:idx])
            root.right = build(inorder[idx+1:n], postorder[idx:n-1])
            return root 
        return build(inorder, postorder)

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        n = len(inorder)
        if n == 0:
            return None
        val = postorder[-1]
        root = TreeNode(val, None, None) 
        idx = 0
        while idx < n:
            if inorder[idx] == val:
                break  
            idx += 1 # !!!
        root.left = self.buildTree(inorder[:idx], postorder[:idx]) 
        root.right = self.buildTree(inorder[idx+1:], postorder[idx:n-1])
        return root

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

思路
- example
- 三生万物，左中右的轮回
- 中前后
- 前中后
- 递归主体思路
  - 建立节点
  - 划分两个数组，分别得到左右子树
  - 递归调用建立左右子树，链接
- 递归函数传递参数: inorder, postorder 数组
- 基本case: 空节点
- 返回值：当前根节点
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        #  preorder: 中左右
        #  inorder : 左中右
        # Base Case
        if len(preorder) == 0:
            return None 
        val = preorder[0]
        root = TreeNode(val)
        # find pivot index in inorder 
        pivot = 0
        for i in range(len(inorder)):
            if inorder[i] == val:
                pivot = i 
                break 
        # partition 
        inorder_left, inorder_right = inorder[:pivot], inorder[pivot+1:]
        size_left, size_right = len(inorder_left), len(inorder_right)
        preorder_left, preorder_right = preorder[1:1+size_left], preorder[1+size_left:]
        # recursive, link
        root.left = self.buildTree(preorder_left, inorder_left)
        root.right = self.buildTree(preorder_right, inorder_right)
        return root

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        n = len(inorder)
        if n == 0:
            return None 
        root = TreeNode(preorder[0])
        val = preorder[0]
        idx = -1
        for i in range(n):
            if inorder[i] == val:
                idx = i 
                break 
        root.left = self.buildTree(preorder[1:idx+1], inorder[0:idx])
        root.right = self.buildTree(preorder[idx+1:n], inorder[idx+1:n])
        return root

最后编辑于：2023.10.07 11:59:32

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,189评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,577评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,857评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,703评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,705评论 5赞 366
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,620评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,995评论 3赞 396
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,656评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,898评论 1赞 298
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,639评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,720评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,395评论 4赞 319
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,982评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,953评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,195评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,907评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,472评论 2赞 342

Day 18 二叉树：513. 底层左下角, 112|113. 路径总和I II, 106. 中序|后序构造, 105. 前序|中序构造

513. 找树左下角的值

112. 路径总和

113. 路径总和 II

106. 从中序与后序遍历序列构造二叉树

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

推荐阅读更多精彩内容