二叉树高频题

原创

王脸小

修改于 2019-11-25 14:19:48

6390

修改于 2019-11-25 14:19:48

文章被收录于专栏：王漂亮王漂亮

二叉树定义

class TreeNode:
    def __int__(self, x):
        self.val = x
        self.left = None
        self.right = None

二叉树遍历

// 遍历框架
def traverse(root):
    if root is None: return
    # 前序遍历代码写在这
    traverse(root.left)
    # 中序遍历代码写在这 
    traverse(root.right)
    # 后序遍历代码写在这

二叉树的构造

297. 序列化与反序列化 - H

Serialize and Deserialize Binary Tree

Example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Solution

DFS比较利于后续deserialize，下面是前序遍历的解法

class Codec:
    def serialize(self, root):
        res = []        
        def helper(node):
            if node:
                res.append(str(node.val))
                helper(node.left)
                helper(node.right)
            else:
                res.append("#")

        helper(root)
        return " ".join(res)
            

    def deserialize(self, data):
        nums = iter(data.split())
        def helper():
            num = next(nums)
            if num == "#": return None
            node = TreeNode(int(num))
            node.left = helper()
            node.right = helper()
            return node
        
        return helper()

144. 二叉树前序遍历

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Solution - 递归解法

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        
        def helper(root):
            if not root: return
            self.res += [root.val]
            helper(root.left)
            helper(root.right)
        
        helper(root)
        
        return self.res

Solution - 迭代解法

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        res, stack = [], []
        
        while stack or root:
            if root:
                res.append(root.val)
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                root = root.right

        return res

94. 二叉树中序遍历

Binary Tree Inorder Traversal

Solution - 递归解法

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        
        def helper(root):
            if not root: return
            helper(root.left)
            self.res += [root.val]
            helper(root.right)
            
        helper(root)
        
        return self.res

Solution - 迭代解法

很容易写错，对比下前序

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return
        res, stack = [], []

        while root or stack:
            
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                res.append(root.val)
                root = root.right
                
        return res

145. 二叉树后序遍历

Binary Tree Postorder Traversal

Solution - 递归解法

class Solution(object):
    def postorderTraversal(self, root):
        self.res = []
        
        def helper(root):
            if not root: return
            
            helper(root.left)
            helper(root.right)
            self.res += [root.val]
            
        helper(root)
        
        return self.res

Solution - 迭代解法(DFS逆序)

从根节点开始依次迭代，然后依次压入它的所有孩子节点，按照从上到下、从左至右的顺序依次压入栈中。

输出是：从上到下，从右到左的(栈的性质)

后序遍历的顺序是从下到上、从左至右，所以需要将输出列表逆序输出。

class Solution:
    def postorderTraversal(self, root: TreeNode):
    
        if not root: return []
        r, stack = [], [root]
        
        while stack:
            root = stack.pop()
            r.append(root.val)
            if root.left: stack.append(root.left)
            if root.right: stack.append(root.right)
            
        return r[::-1]

102. 层序遍历

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7],

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution

别人的解法，单队列

class Solution(object):
    def levelOrder(self, root):
        if not root: return []
        
        res = []
        q = deque([(root, 0)])
        while q:

            node, layer = q.popleft()
            
            if len(res) <= layer: res.append([])
            
            res[layer].append(node.val)
            
            if node.left: q.append((node.left, layer+1))
            if node.right: q.append((node.right, layer+1))
        
        return res

自己的解法，双队列

注意是队列，node = cur.popleft()，先进先出

class Solution(object):
    def levelOrder(self, root):
        if not root: return []
        res = []
        cur, nex = deque([root]), deque()
        cur_vals = []
        
        while cur or nex:
            while cur:
                node = cur.popleft()
                cur_vals.append(node.val)
                if node.left: nex.append(node.left)
                if node.right: nex.append(node.right)

            res.append(cur_vals)
            cur_vals = []
            cur, nex = nex, deque()
            
        return res

103. 锯齿形层次遍历

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree [3,9,20,null,null,15,7],

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Solution

注意是node = cur.pop()，栈，后进先出

class Solution:
    def zigzagLevelOrder(self, root):
        if not root: return []
        res = []
        cur, nex = deque([root]), deque()
        cur_vals = []
        layer = 0
        
        while cur or nex:
            while cur:
                node = cur.pop()
                cur_vals.append(node.val)
                
                if layer%2 == 0:
                    if node.left: nex.append(node.left)
                    if node.right: nex.append(node.right)
                else:
                    if node.right: nex.append(node.right)
                    if node.left: nex.append(node.left)

            res.append(cur_vals)
            cur_vals = []
            cur, nex = nex, deque()
            layer += 1

        return res

二叉树的对角线遍历

Diagonal Traversal of Binary Tree

Diagonal Traversal of binary tree : 
 8 10 14
 3 6 7 13
 1 4

Solution

class Solution():
    def DiagonalOrder(self, root):
        if not root: return []
        res = []
        
        def helper(node, layer):
            if len(res) < layer+1:
                res.append([])
            res[layer].append(node.val)
            if node.left: helper(node.left, layer+1)
            if node.right: helper(node.right, layer)
        helper(root, 0)
        return res

105. 前序与中序构造二叉树

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

Solution

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder: return None
        
        idx = inorder.index(preorder[0])
        node = TreeNode(preorder[0])
        node.left = self.buildTree(preorder[1:idx+1], inorder[:idx])
        node.right = self.buildTree(preorder[idx+1:], inorder[idx+1:])
        
        return node

106. 中序与后序构造二叉树

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

Solution

class Solution(object):
    def buildTree(self, inorder, postorder):
        if not inorder: return None
        
        root = TreeNode(postorder[-1])
        idx = inorder.index(root.val
        root.left = self.buildTree(inorder[:idx], postorder[:idx])
        root.right = self.buildTree(inorder[idx+1:], postorder[idx:-1])
        
        return root

高频题目

101. 对称二叉树

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Solution

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        
        def isMatch(left, right):
            
            if not left and not right: return True
            if not left or not right: return False
        
            return left.val == right.val 
                   and isMatch(left.left, right.right) 
                   and isMatch(left.right, right.left)
        
        return isMatch(root, root)

116. 填充每个节点的下一个右侧节点指针

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

Solution

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        
        if root and root.left:
            root.left.next = root.right
            
            if root.next:
                root.right.next = root.next.left
                
            self.connect(root.left)
            self.connect(root.right)
            
        return root

对于任意一次递归，只需要考虑如何设置子节点的 next 属性：

将左子节点连接到右子节点
将右子节点连接到 root.next 的左子节点
递归左右节点

117. 填充每个节点的下一个右侧节点指针 II

Given a binary tree

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

Solution

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        
        if root and (root.left or root.right):
            if root.left and root.right:
                root.left.next = root.right
            
            node = root.right or root.left
            
            head = root.next
            while head and not (head.left or head.right):
                head = head.next
            node.next = head and (head.left or head.right)
                    
            self.connect(root.right)
            self.connect(root.left)
         
         return root

对于任意一次递归，只考虑如何设置子节点的 next 属性,分为三种情况：
没有子节点：直接返回
有一个子节点：将这个子节点的 next 属性设置为同层的下一个节点，即为 root.next 的最左边的一个节点，如果 root.next 没有子节点，则考虑 root.next.next，依次类推
有两个节点：左子节点指向右子节点，然后右子节点同第二种情况的做法
注意递归的顺序需要从右到左

104. 二叉树的最大深度

Path Sum II

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its depth = 3.

Solution

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example 1:

Input: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Solution

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        left = {}
        self.res = 0
        
        def dfs(node, depth, pos):
            if not node: return
            if depth not in left: left[depth] = pos
            self.res = max(self.res, pos-left[depth]+1)
            dfs(node.left, depth+1, pos*2)
            dfs(node.right, depth+1, pos*2+1)
            
        dfs(root, 0, 0)
        return self.res

思路：抄的，每层碰到的第一个节点为left，接下来的每个该层节点-left为该层的potential宽度，取max则为最大宽度。

543.二叉树的直径

Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example: Given a binary tree

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Solution

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.res = 1
        
        def maxgain(root):
            if not root: return 0
            
            left = maxgain(root.left)
            right = maxgain(root.right)
            self.res = max(left + right + 1, self.res)
            
            return max(left, right) + 1
        
        maxgain(root)
        
        return self.res - 1

236. 二叉树的最近公共祖先

Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Solution

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        def helper(root):
            if not root: return 0
            
            mid = 1 if root == q or root == p else 0
            left = helper(root.left) 
            right = helper(root.right)
            
            if left + right + mid >=2 : self.res = root
            
            return left or right or mid
            
        helper(root)
        return self.res

113. 路径总和 II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

Solution

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        if not root: return []
        res = []
        
        def countSum(root, sum, track):
            if not root: return
            if root.val == sum and not (root.left or root.right):
                res.append(track+[root.val])
                
            countSum(root.left, sum-root.val, track+[root.val])
            countSum(root.right, sum-root.val, track+[root.val])
            
        countSum(root, sum, [])
        
        return res

437.路径总和 III

Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Solution

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        if not root: return 0
        return self.CountSum(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
    
    def CountSum(self, root, sum):
        if not root: return 0
        return (root.val == sum) 
            + self.CountSum(root.left, sum-root.val) 
            + self.CountSum(root.right, sum-root.val)

124. 最大路径和 - H

Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7
 
Output: 42

Solution

Reference, root_gain = root+max(left_gain, right_gain)

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        
        self.res = float("-inf")
        
        def maxGain(root):
            if not root: return 0
            
            left = max(maxGain(root.left), 0)
            right = max(maxGain(root.right), 0)
            self.res = max(self.res, left + right + root.val)
            
            return max(left, right) + root.val
        
        maxGain(root)
        return self.res

11.4 抄了抄，似懂非懂，递归真强大。

11.6 寄己简化了下，优秀

二叉搜索树

98. 验证二叉搜索树

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

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

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Solution

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:

        def helper(root, low = float("-inf"), high = float("inf")):
            if not root: return True
            if root.val <= low or root.val >= high: 
                return False
            
            return helper(root.left, low, root.val) and helper(root.right, root.val, high)
        
        return helper(root)

426. BST转排序的双向链表

将一个二叉搜索树就地转化为一个已排序的双向循环链表。可以将左右孩子指针作为双向循环链表的前驱和后继指针。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

Solution

本质就是中序遍历，只不过遍历到当前节点要做点事情: last.right = cur, cur.left = last

first是全局first节点，last是当前遍历到的last节点

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root: return None
        first, last = None, None
        
        def inorder(node):
            if not node: return
            nonlocal first, last
            
            inorder(node.left)
            
            # 遍历当前做的事情
            if first:
                last.right, node.left = node, last
            else:
                first = node
            last = node
            
            inorder(node.right)
        
        inorder(root)
        last.right, first.left = first, last
        
        return first

450. 删除BST中的节点 - M

Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Solution

⭐二叉搜索树操作集锦⭐

11.6 抄的，removemax还没来得及看。

11.7 改了下多余的代码，可以再熟悉一下

通过二叉树模板找到target之后，删除分三种情况：没有子节点(直接删除)；有一个子节点(直接继承)，有两个子节点

class Solution:
    def remove_max(self, node):
        if not node.right:
            new_root = node.left
            return new_root
        node.right = self.remove_max(node.right)
        return node

    def max(self, node):
        while node.right:
            node = node.right
        return node


    def deleteNode(self, root, key):
        if not root: return None
        
        if root.val > key: root.left = self.deleteNode(root.left, key)
        if root.val < key: root.right = self.deleteNode(root.right, key)
        
        if root.val == key:
            if not root.left and not root.right: return None
            if not root.left or not root.right: return root.left or root.right
            
            pre = self.max(root.left)
            pre.left = self.remove_max(root.left)
            pre.right = root.right
            return pre
        
        return root

删除区间内的节点

Delete Node within a range

Solution

本质是后序遍历(保证当前节点的子树们已经被fix)，只不过在当前节点要做点事情(fix当前节点)

两种情况: 节点比min小，用右节点顶替root；节点比max大，用作节点顶替root。

class Solution(object):
    def removeOutsideRange(self, root, minval, maxval):
        if not root: return None
        
        root.left = self.removeOutsideRange(root.left, minval, maxval)
        root.right = self.removeOutsideRange(root.right, minval, maxval)

        if root.val < minval:
            new_root = root.right
            return new_root
        if root.val > maxval:
            new_root = root.left
            return new_root

        return root

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

二叉树

python

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

二叉树

python