Skip to content

Binary Tree

Table of Contents

298. Binary Tree Longest Consecutive Sequence

from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


# Binary Tree
def longestConsecutive(root: Optional[TreeNode]) -> int:
    res = 0

    def dfs(node):
        if not node:
            return 0

        left, right = dfs(node.left), dfs(node.right)
        cur = 1
        if node.left and node.left.val == (node.val + 1):
            cur = max(cur, left + 1)
        if node.right and node.right.val == (node.val + 1):
            cur = max(cur, right + 1)

        nonlocal res
        res = max(res, cur)
        return cur

    dfs(root)

    return res


if __name__ == "__main__":
    root = build([1, 3, 2, 4, None, None, None, 5])
    print(root)
    #       1
    #      / \
    #     3   2
    #    /
    #   4
    #  /
    # 5
    print(longestConsecutive(root))  # 3

549. Binary Tree Longest Consecutive Sequence II

250. Count Univalue Subtrees

1120. Maximum Average Subtree

545. Boundary of Binary Tree

366. Find Leaves of Binary Tree

from collections import defaultdict
from typing import List, Optional

from binarytree import Node as TreeNode
from binarytree import build


def findLeaves(root: Optional[TreeNode]) -> List[List[int]]:
    depths = defaultdict(list)

    def dfs(node):
        if not node:
            return 0
        l, r = dfs(node.left), dfs(node.right)
        depth = 1 + max(l, r)
        depths[depth].append(node.val)
        return depth

    dfs(root)
    return [i for i in depths.values()]


if __name__ == "__main__":
    root = build([1, 2, 3, 4, 5])
    print(root)
    #     __1
    #    /   \
    #   2     3
    #  / \
    # 4   5
    print(findLeaves(root))  # [[4, 5, 3], [2], [1]]

314. Binary Tree Vertical Order Traversal

  • LeetCode | 力扣

  • Tags: Hash Table, Tree, Depth First Search, Breadth First Search, Sorting, Binary Tree

Comments