二叉树定义
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)
# 后序遍历代码写在这
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()
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
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
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]
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
自己的解法,双队列
注意是队列,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
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
注意是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
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
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
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)
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 属性:
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
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
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则为最大宽度。
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
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
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
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)
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 寄己简化了下,优秀
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
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)
将一个二叉搜索树就地转化为一个已排序的双向循环链表。可以将左右孩子指针作为双向循环链表的前驱和后继指针。
为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“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
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:
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
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 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。