# 二叉树高频题

```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],

```    3
/ \
9  20
/  \
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```

```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]`,

```    3
/ \
9  20
/  \
15   7```

return its zigzag level order traversal as:

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

Solution

```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:

```    3
/ \
9  20
/  \
15   7```

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:

```    3
/ \
9  20
/  \
15   7```

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:

```    1
/ \
2   2
/ \ / \
3  4 4  3```

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

```    1
/ \
2   2
\   \```

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```

• 将左子节点连接到右子节点
• 将右子节点连接到 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

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],

```    3
/ \
9  20
/  \
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```

## 662. 二叉树最大宽度

Maximum Width of Binary Tree

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```

## 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

```          1
/ \
2   3
/ \
4   5    ```

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转排序的双向链表

Solution

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:

1. Search for a node to remove.
2. 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 改了下多余的代码，可以再熟悉一下

```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

```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```

0 条评论

• ### 图：拓扑排序/Union Find高频题

3. while q.pop, 减少当前node的outdegree中节点的indegree，当indegree为零append到q

• ### Board相关题

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands...

• ### 链表高频题

总结：所有链表题目都做过而且都Accept了，不排除有些是抄的。。leet, leet-cn

• ### Golang Leetcode 230. Kth Smallest Element in a BST.go

版权声明：原创勿转 https://blog.csdn.net/anakinsun/article/details/89043444

• ### BST & AVL 二分搜索树 & 平衡二叉树的实现原理

本文完整的实现了基本的BST，由于注重的是逻辑和原理的实现，所以没有采用泛型。注意方法的访问修饰符。

• ### 如何使用CP / SCP / RSYNC在Linux中排除特定目录？

对于任何系统管理员或一般Linux操作系统用户而言，在服务器之间执行文件复制操作都是一项常见任务。在将文件从一个系统复制到另一个系统时，由于某些特定原因，我们可...

• ### Linux操作系统启动流程梳理

接触linux系统运维已经好几年了，常常被问到linux系统启动流程问题，刚好今天有空来梳理下这个过程： 一般来说，所有的操作系统的启动流程基本就是： ? 总的...

• ### leecode刷题（24）-- 翻转二叉树

二叉树问题，我们首先要想到的使用递归的方式来解决，有了这个思路，处理这道问题就很简单了：先互换根节点的左右节点，然后递归地处理左子树，再递归地处理右子树，直到所...