Trees

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

Treesも最初は独特な感じがしたけど、そんなにパターンはないので、一度慣れておくのが大事だと思う。この後のGraphとかDPとかノード探索や再帰関連の問題に必須な知識でもある。

46. Invert Binary Tree

Problem

You are given the root of a binary tree root. Invert the binary tree and return its root.

Example 1:

Input: root = [1,2,3,4,5,6,7]

Output: [1,3,2,7,6,5,4]

Copy

Example 2:

Input: root = [3,2,1]

Output: [3,1,2]

Copy

Example 3:

Input: root = []

Output: []

Copy

Constraints:

• 0 <= The number of nodes in the tree <= 100.
• -100 <= Node.val <= 100

Solution

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

47. Maximum Depth of Binary Tree

Problem

Given the root of a binary tree, return its depth.

The depth of a binary tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [1,2,3,null,null,4]

Output: 3

Copy

Example 2:

Input: root = []

Output: 0

Copy

Constraints:

• 0 <= The number of nodes in the tree <= 100.
• -100 <= Node.val <= 100

Solution

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)

        return 1 + max(left_depth, right_depth)

48. Diameter of Binary Tree

Problem

The diameter of a binary tree is defined as the length of the longest path between any two nodes within the tree. The path does not necessarily have to pass through the root.

The length of a path between two nodes in a binary tree is the number of edges between the nodes.

Given the root of a binary tree root, return the diameter of the tree.

Example 1:

Input: root = [1,null,2,3,4,5]

Output: 3

Copy

Explanation: 3 is the length of the path [1,2,3,5] or [5,3,2,4].

Example 2:

Input: root = [1,2,3]

Output: 2

Copy

Constraints:

• 1 <= number of nodes in the tree <= 100
• -100 <= Node.val <= 100

Solution

# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        max_length = 0

        def dfs(node: TreeNode) -> int:
            nonlocal max_length
            
            if not node:
                return 0
            
            left_depth = dfs(node.left)
            right_depth = dfs(node.right)

            max_length = max(max_length, left_depth + right_depth)

            return 1 + max(left_depth, right_depth)
        
        dfs(root)
        return max_length

49. Balanced Binary Tree

Problem

Given a binary tree, return true if it is height-balanced and false otherwise.

A height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [1,2,3,null,null,4]

Output: true

Copy

Example 2:

Input: root = [1,2,3,null,null,4,null,5]

Output: false

Copy

Example 3:

Input: root = []

Output: true

Copy

Constraints:

• The number of nodes in the tree is in the range [0, 1000].
• -1000 <= Node.val <= 1000

Solution

# 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:
        
        def dfs(node: TreeNode) -> int:
            if not node:
                return 0
            
            left_depth = dfs(node.left)
            right_depth = dfs(node.right)
            
            # rootだけの話ではなく各ノードの左右のdepthの差を見なきゃいけないので
            # それぞれどちらかが-1だったらhight-balancedでない
            if left_depth == -1 or right_depth == -1:
                return -1

            # 左右のdepthの差が1より大きければ-1を返すルールにするとシンプルに書ける
            if abs(left_depth - right_depth) > 1:
                return -1

            return 1 + max(left_depth, right_depth)

        return dfs(root) != -1

50. Same Tree

Problem

Given the roots of two binary trees p and q, return true if the trees are equivalent, otherwise return false.

Two binary trees are considered equivalent if they share the exact same structure and the nodes have the same values.

Example 1:

Input: p = [1,2,3], q = [1,2,3]

Output: true

Copy

Example 2:

Input: p = [4,7], q = [4,null,7]

Output: false

Copy

Example 3:

Input: p = [1,2,3], q = [1,3,2]

Output: false

Copy

Constraints:

• 0 <= The number of nodes in both trees <= 100.
• -100 <= Node.val <= 100

Solution

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        
        if not p or not q:
            return False
        
        if p.val != q.val:
            return False
        
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

51. Subtree of a Binary Tree

Problem

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Example 1:

Input: root = [1,2,3,4,5], subRoot = [2,4,5]

Output: true

Copy

Example 2:

Input: root = [1,2,3,4,5,null,null,6], subRoot = [2,4,5]

Output: false

Copy

Constraints:

• 0 <= The number of nodes in both trees <= 100.
• -100 <= root.val, subRoot.val <= 100

Solution

# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        
        def isSameTree(p: TreeNode, q: TreeNode) -> bool:
            if not p and not q:
                return True
            
            if not p or not q:
                return False
            
            if p.val != q.val:
                return False
            
            return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

        if not root and not subRoot:
            return True
        
        if not root or not subRoot:
            return False
        
        if isSameTree(root, subRoot):
            return True
        
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

52. Lowest Common Ancestor of a Binary Search Tree

Problem

Given a binary search tree (BST) where all node values are unique, and two nodes from the tree p and q, return the lowest common ancestor (LCA) of the two nodes.

The lowest common ancestor between two nodes p and q is the lowest node in a tree T such that both p and q as descendants. The ancestor is allowed to be a descendant of itself.

Example 1:

Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 8

Output: 5

Copy

Example 2:

Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 4

Output: 3

Copy

Explanation: The LCA of nodes 3 and 4 is 3, since a node can be a descendant of itself.

Constraints:

• 2 <= The number of nodes in the tree <= 100.
• -100 <= Node.val <= 100
• p != q
• p and q will both exist in the BST.

Solution

# 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 lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        while root:
            if root.val < p.val and root.val < q.val:
                root = root.right
            elif root.val > p.val and root.val > q.val:
                root = root.left
            else:
                return root

53. Binary Tree Level Order Traversal

Problem

Given a binary tree root, return the level order traversal of it as a nested list, where each sublist contains the values of nodes at a particular level in the tree, from left to right.

Example 1:

Input: root = [1,2,3,4,5,6,7]

Output: [[1],[2,3],[4,5,6,7]]

Copy

Example 2:

Input: root = [1]

Output: [[1]]

Copy

Example 3:

Input: root = []

Output: []

Copy

Constraints:

• 0 <= The number of nodes in both trees <= 1000.
• -1000 <= Node.val <= 1000

Solution

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        queue = deque()
        if root:
            queue.append(root)
        
        res = []

        while queue:
            q_size = len(queue)
            each_level = []
            for i in range(q_size):
                top = queue.popleft()
                each_level.append(top.val)

                if top.left:
                    queue.append(top.left)
                
                if top.right:
                    queue.append(top.right)

            res.append(each_level)
        
        return res

54. Binary Tree Right Side View

Problem

Given a binary tree root, return the level order traversal of it as a nested list, where each sublist contains the values of nodes at a particular level in the tree, from left to right.

Example 1:

Input: root = [1,2,3,4,5,6,7]

Output: [[1],[2,3],[4,5,6,7]]

Copy

Example 2:

Input: root = [1]

Output: [[1]]

Copy

Example 3:

Input: root = []

Output: []

Copy

Constraints:

• 0 <= The number of nodes in both trees <= 1000.
• -1000 <= Node.val <= 1000

Solution

# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        queue = deque()
        if root:
            queue.append(root)
        res = []

        while queue:
            q_size = len(queue)
            for i in range(q_size):
                node = queue.popleft()

                if i == q_size - 1:
                    res.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                
                if node.right:
                    queue.append(node.right)
        
        return res

55. Count Good Nodes In Binary Tree

Problem

Within a binary tree, a node x is considered good if the path from the root of the tree to the node x contains no nodes with a value greater than the value of node x

Given the root of a binary tree root, return the number of good nodes within the tree.

Example 1:

Input: root = [2,1,1,3,null,1,5]

Output: 3

Copy

Example 2:

Input: root = [1,2,-1,3,4]

Output: 4

Copy

Constraints:

• 1 <= number of nodes in the tree <= 100
• -100 <= Node.val <= 100

Solution

# 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 goodNodes(self, root: TreeNode) -> int:
        
        def dfs(node: TreeNode, max_val_sofar: int) -> int:
            if not node:
                return 0
            
            res = 0
            if node.val >= max_val_sofar:
                res +=1
                max_val_sofar = node.val
            
            left_good_nodes = dfs(node.left, max_val_sofar)
            right_good_nodes = dfs(node.right, max_val_sofar)
            res += left_good_nodes
            res += right_good_nodes

            return res
        
        return dfs(root, -math.inf)

56. Validate Binary Search Tree

Problem

Given the root of a binary tree, return true if it is a valid binary search tree, otherwise return false.

A valid binary search tree satisfies the following constraints:

• The left subtree of every node contains only nodes with keys less than the node's key.
• The right subtree of every node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees are also binary search trees.

Example 1:

Input: root = [2,1,3]

Output: true

Copy

Example 2:

Input: root = [1,2,3]

Output: false

Copy

Explanation: The root node's value is 1 but its left child's value is 2 which is greater than 1.

Constraints:

• 1 <= The number of nodes in the tree <= 1000.
• -1000 <= Node.val <= 1000

Solution

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        def dfs(node: TreeNode, min_val: int, max_val: int) -> bool:
            if not node:
                return True
            
            if not min_val < node.val < max_val:
                return False
            
            if not dfs(node.left, min_val, node.val):
                return False
            
            if not dfs(node.right, node.val, max_val):
                return False
            
            return True
        
        return dfs(root, -math.inf, math.inf)

57. Kth Smallest Element In a Bst

Problem

Given the root of a binary tree, return true if it is a valid binary search tree, otherwise return false.

A valid binary search tree satisfies the following constraints:

• The left subtree of every node contains only nodes with keys less than the node's key.
• The right subtree of every node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees are also binary search trees.

Example 1:

Input: root = [2,1,3]

Output: true

Copy

Example 2:

Input: root = [1,2,3]

Output: false

Copy

Explanation: The root node's value is 1 but its left child's value is 2 which is greater than 1.

Constraints:

• 1 <= The number of nodes in the tree <= 1000.
• -1000 <= Node.val <= 1000

Solution

再帰

# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        inorder_nodes = []

        def inorder(node: TreeNode) -> None:
            if not node:
                return
            
            inorder(node.left)
            inorder_nodes.append(node.val)
            inorder(node.right)
        
        inorder(root)
        return inorder_nodes[k-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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        curr = root
        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            
            top = stack.pop()
            k -= 1
            if k == 0:
                return top.val
            
            curr = top.right

58. Construct Binary Tree From Preorder And Inorder Traversal

Problem

Given the root of a binary tree, return true if it is a valid binary search tree, otherwise return false.

A valid binary search tree satisfies the following constraints:

• The left subtree of every node contains only nodes with keys less than the node's key.
• The right subtree of every node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees are also binary search trees.

Example 1:

Input: root = [2,1,3]

Output: true

Copy

Example 2:

Input: root = [1,2,3]

Output: false

Copy

Explanation: The root node's value is 1 but its left child's value is 2 which is greater than 1.

Constraints:

• 1 <= The number of nodes in the tree <= 1000.
• -1000 <= Node.val <= 1000

Solution

Time Complexity: O(N^2)

inorder.index で検索する部分で余計に時間がかかってるが、直感的に理解しやすい。

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        
        root = TreeNode(preorder[0])
        middle_i = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:middle_i+1], inorder[:middle_i])
        root.right = self.buildTree(preorder[middle_i+1:], inorder[middle_i+1:])

        return root

Time Complexity: O(N)

inorderのリストの値とindexを事前にhash_mapに保存しておき、かつスライスをやめれば速くなる。

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        val_i_inorder_map = { v: i for i, v in enumerate(inorder) }

        def dfs(pre_left: int, pre_right: int, in_left: int, in_right: int) -> TreeNode:

            if pre_left > pre_right:
                return None
            
            root_val = preorder[pre_left]
            root = TreeNode(root_val)
            middle_i = val_i_inorder_map[root_val]
            left_tree_size = middle_i - in_left

            root.left = dfs(pre_left+1, pre_left + left_tree_size, in_left, middle_i-1)
            root.right = dfs(pre_left+left_tree_size+1, pre_right, middle_i+1, in_right)

            return root

        return dfs(0, len(preorder)-1, 0, len(inorder)-1)

59. Binary Tree Maximum Path Sum

Problem

Given the root of a non-empty binary tree, return the maximum path sum of any non-empty path.

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can not appear in the sequence more than once. The path does not necessarily need to include the root.

The path sum of a path is the sum of the node's values in the path.

Example 1:

Input: root = [1,2,3]

Output: 6

Copy

Explanation: The path is 2 -> 1 -> 3 with a sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-15,10,20,null,null,15,5,-5]

Output: 40

Copy

Explanation: The path is 15 -> 20 -> 5 with a sum of 15 + 20 + 5 = 40.

Constraints:

• 1 <= The number of nodes in the tree <= 1000.
• -1000 <= Node.val <= 1000

Solution

# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
        max_sum = -math.inf

        def dfs(node: TreeNode) -> int:
            nonlocal max_sum
            
            if not node:
                return 0
            
            left_sum = dfs(node.left)
            right_sum = dfs(node.right)

            path_sum = node.val + left_sum + right_sum
            max_sum = max(max_sum, path_sum)

            res = node.val + max(left_sum, right_sum)
            if res < 0:
                return 0
            else:
                return res
        
        dfs(root)
        return max_sum

60. Serialize And Deserialize Binary Tree

Problem

Implement an algorithm to serialize and deserialize a binary tree.

Serialization is the process of converting an in-memory structure into a sequence of bits so that it can be stored or sent across a network to be reconstructed later in another computer environment.

You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. There is no additional restriction on how your serialization/deserialization algorithm should work.

Note: The input/output format in the examples is the same as how NeetCode serializes a binary tree. You do not necessarily need to follow this format.

Example 1:

Input: root = [1,2,3,null,null,4,5]

Output: [1,2,3,null,null,4,5]

Copy

Example 2:

Input: root = []

Output: []

Copy

Constraints:

• 0 <= The number of nodes in the tree <= 1000.
• -1000 <= Node.val <= 1000

Solution

# 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 Codec:
    
    # Encodes a tree to a single string.
    def serialize(self, root: Optional[TreeNode]) -> str:
        res = []

        def preorder(node: TreeNode) -> None:
            nonlocal res
            if not node:
                res.append('N')
                return
            
            res.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
        
        preorder(root)
        return ','.join(res)
        
    # Decodes your encoded data to tree.
    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data:
            return None
        
        values = data.split(',')

        i = 0
        def dfs() -> None:
            nonlocal i
            if values[i] == 'N':
                i += 1
                return None
            
            res = TreeNode(int(values[i]))
            
            i += 1
            res.left = dfs()
            res.right = dfs()

            return res
        
        return dfs()