本文汇总了 LeetCode 及剑指 Offer 中关于二叉树的经典算法题目，涵盖左叶子之和、N 叉树层序遍历、路径总和、删除节点、找左下角值、最小绝对差、构造二叉树、累加树转换、直径计算、边界遍历、合并二叉树、最长同值路径、搜索与插入、距离 K 节点、范围求和、完全性检查、苹果收集、随机指针克隆、奇偶树判断、最近公共祖先、子树平均值、子结构判断、后序遍历验证、双向链表转换、平衡二叉树判断及下一个节点查找。提供 C++ 与 Python 代码实现及复杂度分析。
计算给定二叉树的所有左叶子之和。
Given the root of a binary tree, return the sum of all left leaves. A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24。
前序遍历过程中添加记录左叶子节点的值。在递归过程中，我们使用一个标志位 from_left 来记录当前节点是否为上一层递归节点的左子节点。
Record the values of left leaf nodes during the preorder traversal. In the recursive process, we use a flag from_left to record whether the current node is the left child node of the recursive node in the upper level.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dfs(TreeNode* root, bool from_left) {
if (!root) return;
bool is_leaf = !root->left && !root->right;
if (is_leaf && from_left) res += root->val;
dfs(root->left, true);
dfs(root->right, false);
}
int sumOfLeftLeaves(TreeNode* root) {
bool from_left = false;
dfs(root, from_left);
return res;
}
private:
int res;
};
# 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 __init__(self):
self.res = 0
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
self.core(root, False)
return self.res
def core(self, root, from_left):
if not root: return
if from_left and root.left is None and root.right is None:
self.res += root.val
self.core(root.left, True)
self.core(root.right, False)
迭代版本
class Solution {
public:
bool is_leaf(TreeNode* root) {
if (!root) return false;
return !root->left && !root->right;
}
int sumOfLeftLeaves(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> q;
q.push(root);
int res = 0;
while (!q.empty()) {
auto node = q.front(); q.pop();
if (node->left) {
if (is_leaf(node->left)) res += node->left->val;
else q.push(node->left);
}
if (node->right) {
if (!is_leaf(node->right)) q.push(node->right);
}
}
return res;
}
};
from collections import deque
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
def is_leaf(root):
if not root: return None
return not root.left and not root.right
q = deque()
q.append(root)
res = 0
while q:
node = q.popleft()
if node.left:
if is_leaf(node.left): res += node.left.val
else: q.append(node.left)
if node.right:
if not is_leaf(node.right): q.append(node.right)
return res
时间复杂度：O(n) 空间复杂度：O(n)
Given an n-ary tree, return the level order traversal of its nodes' values. Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.
Input: root = [1,null,3,2,4,null,5,6] Output: [[1],[3,2,4],[5,6]]
正常层次遍历解决问题。
import queue
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
res = []
if not root: return res
q = queue.Queue()
q.put(root)
while not q.empty():
length = q.qsize()
res_sub = []
for i in range(length):
node = q.get()
for child in node.children:
q.put(child)
res_sub.append(node.val)
res.append(res_sub)
return res
Time Complexity: O(n) Space Complexity: O(n)
给定一个二叉树，它的每个结点都存放着一个整数值。 找出路径和等于给定数值的路径总数。 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 二叉树不超过 1000 个节点，且节点数值范围是 [-1000000, 1000000] 的整数。
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start or end at the root or a leaf, but it must go downwards.
示例：root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 返回 3。和等于 8 的路径有:
这个题明确提出路径前缀和以及 hash_map 组合解决问题。记录每条路径的累积和，如果发现当前累积和-target 在之前出现过，那么之前的路径集合中一定存在 target 的路径。
Solve the problem by combining prefix sum with a hash map. The hash map records the cumulative sum of each path; if it is found that the current cumulative sum minus the target has appeared before, then there must be a path equal to the target in the previous path set.
class Solution {
public:
int pathSum(TreeNode* root, int targetSum) {
m[0] = 1;
core(0, root, targetSum);
return res;
}
void core(long cur_sum, TreeNode* root, int targetSum) {
if (!root) return;
cur_sum += root->val;
if (m.find(cur_sum - targetSum) != m.end()) {
res += m[cur_sum - targetSum];
}
++m[cur_sum];
core(cur_sum, root->left, targetSum);
core(cur_sum, root->right, targetSum);
--m[cur_sum];
}
private:
unordered_map<long, int> m;
int res = 0;
};
from collections import defaultdict
class Solution:
def __init__(self):
self.m = defaultdict(int)
self.res = 0
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
if not root: return 0
self.m[0] = 1
self.core(0, root, targetSum)
return self.res
def core(self, cur_sum, root, targetSum):
if not root: return
cur_sum += root.val
if self.m[cur_sum - targetSum] != 0:
self.res += self.m[cur_sum - targetSum]
self.m[cur_sum] += 1
self.core(cur_sum, root.left, targetSum)
self.core(cur_sum, root.right, targetSum)
self.m[cur_sum] -= 1
代码中 m[0]=1 的意义在于，能够正确记录从根节点开始，路径之和为 targetSum 的路径。
时间复杂度：O(n)，遍历一次树的时间 空间复杂度：O(n)，最坏情况下树为一个单向链表，这时递归深度为树的节点个数
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
二叉树递归解决问题。
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (root->val > key) { root->left = deleteNode(root->left, key); return root; }
if (root->val < key) { root->right = deleteNode(root->right, key); return root; }
if (!root->left && !root->right) return nullptr;
if (!root->left) return root->right;
if (!root->right) return root->left;
TreeNode* succ = root->right;
while (succ->left) succ = succ->left;
root->right = deleteNode(root->right, succ->val);
root->val = succ->val;
return root;
}
};
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root: return None
if root.val > key: root.left = self.deleteNode(root.left, key); return root
if root.val < key: root.right = self.deleteNode(root.right, key); return root
if not root.left and not root.right: return None
if not root.left: return root.right
if not root.right: return root.left
succ = root.right
while succ.left: succ = succ.left
root.right = self.deleteNode(root.right, succ.val)
root.val = succ.val
return root
时间复杂度：O(n) 空间复杂度：O(n)
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
auto cur = root;
TreeNode* cur_p = nullptr;
while (cur && cur->val != key) {
cur_p = cur;
if (cur->val < key) cur = cur->right;
else cur = cur->left;
}
if (!cur) return root;
if (!cur->left && !cur->right) cur = nullptr;
else if (!cur->left) cur = cur->right;
else if (!cur->right) cur = cur->left;
else {
auto cur_succ = cur->right;
auto succ_p = cur;
while (cur_succ->left) { succ_p = cur_succ; cur_succ = cur_succ->left; }
if (succ_p->val == cur->val) succ_p->right = cur_succ->right;
else succ_p->left = cur_succ->right;
cur_succ->left = cur->left; cur_succ->right = cur->right; cur = cur_succ;
}
if (!cur_p) return cur;
else {
if (cur_p->left && cur_p->left->val == key) cur_p->left = cur;
else cur_p->right = cur;
return root;
}
}
};
时间：O(n) 空间：O(1)
给定一个二叉树的根节点 root，请找出该二叉树的最底层最左边节点的值。 假设二叉树中至少有一个节点。
后序遍历，先遍历左子树，再遍历右子树，最左下方的节点肯定被优先遍历到。
class Solution {
public:
void dfs(TreeNode* root, int height, int& curVal, int& curHeight) {
if (!root) return;
++height;
dfs(root->left, height, curVal, curHeight);
dfs(root->right, height, curVal, curHeight);
if (height > curHeight) { curHeight = height; curVal = root->val; }
}
int findBottomLeftValue(TreeNode* root) {
int curVal = 0, curHeight = 0;
dfs(root, 0, curVal, curHeight);
return curVal;
}
};
class Solution:
def __init__(self):
self.cur_val = 0
self.cur_height = 0
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
if not root: return None
self.core(root, 0)
return self.cur_val
def core(self, root, height):
if not root: return
height += 1
self.core(root.left, height)
self.core(root.right, height)
if height > self.cur_height:
self.cur_height = height
self.cur_val = root.val
迭代法层次遍历，每层第一次 pop 元素时更新 res，遍历完成后 res 即为最终结果。
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
int ret = 0;
while (!q.empty()) {
auto p = q.front(); q.pop();
if (p->right) q.push(p->right);
if (p->left) q.push(p->left);
ret = p->val;
}
return ret;
}
};
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
if not root: return None
q = queue.Queue()
q.put(root)
res = root.val
while not q.empty():
length = q.qsize()
for i in range(length):
node = q.get()
if node.left: q.put(node.left)
if node.right: q.put(node.right)
if i == 0: res = node.val
return res
时间：O(n) 空间：O(n)
Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
中序遍历过程中记录最小差值。
class Solution {
public:
int minDiffInBST(TreeNode* root) {
int res = INT_MAX;
stack<TreeNode*> stk;
bool flag = false;
int last = 0;
while (root || !stk.empty()) {
while (root) { stk.push(root); root = root->left; }
if (!stk.empty()) {
TreeNode* node = stk.top(); stk.pop();
if (flag && node->val - last < res) res = node->val - last;
root = node->right;
last = node->val;
flag = true;
}
}
return res;
}
};
import math
class Solution:
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
flag = False
last_value = -1
res = math.inf
stk = []
while root or len(stk) > 0:
while root:
stk.append(root)
root = root.left
node = stk.pop()
if flag: res = min(res, node.val - last_value)
root = node.right
flag = True
last_value = node.val
return res
递归形式
class Solution {
public:
void dfs(TreeNode* root, int& pre, int& ans) {
if (root == nullptr) return;
dfs(root->left, pre, ans);
if (pre != -1) ans = min(ans, root->val - pre);
pre = root->val;
dfs(root->right, pre, ans);
}
int minDiffInBST(TreeNode* root) {
int ans = INT_MAX, pre = -1;
dfs(root, pre, ans);
return ans;
}
};
import math
class Solution:
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
ans = math.inf
pre = -1
def dfs(root):
nonlocal ans, pre
if not root: return
dfs(root.left)
if pre != -1: ans = min(ans, root.val - pre)
pre = root.val
dfs(root.right)
dfs(root)
return ans
时间复杂度：O(n) 空间复杂度：O(n)
You need to construct a binary tree from a string consisting of parenthesis and integers.
Input: s = "4(2(3)(1))(6(5))" Output: [4,2,6,3,1,5]
dfs + 栈 解决问题。
class Solution:
def gen_node(self, num, stk):
node = TreeNode(int(num)) if num else None
if stk:
if not stk[-1].left: stk[-1].left = node
elif not stk[-1].right: stk[-1].right = node
if node: stk.append(node)
return ''
def str2tree(self, s: str) -> Optional[TreeNode]:
num, stk = '', []
for i in s:
if i == '(': num = self.gen_node(num, stk)
elif i == ')': num = self.gen_node(num, stk); stk.pop()
else: num += i
return stk[-1] if stk else None if not s else TreeNode(int(s))
Time Complexity: O(n) Space Complexity: O(n)
给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
反序二叉树中序遍历解决问题。
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
if (root) {
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
}
return root;
}
private:
int sum = 0;
};
class Solution:
def __init__(self):
self.cur_res = 0
def core(self, root):
if not root: return
self.core(root.right)
self.cur_res += root.val
root.val = self.cur_res
self.core(root.left)
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.core(root)
return root
迭代 反向中序遍历
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
int sum = 0;
stack<TreeNode*> stk;
auto cur = root;
while (!stk.empty() || cur) {
while (cur) { stk.push(cur); cur = cur->right; }
if (!stk.empty()) {
auto node = stk.top(); stk.pop();
sum += node->val;
node->val = sum;
cur = node->left;
}
}
return root;
}
};
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
cur = root
s = 0
stk = []
while cur or len(stk) > 0:
while cur: stk.append(cur); cur = cur.right
node = stk.pop()
s += node.val
node.val = s
cur = node.left
return root
时间复杂度：O(n) 空间复杂度：O(n)
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 注意：两结点之间的路径长度是以它们之间边的数目表示。
通过 dfs 来记录以 root 为终止节点的最长路径对应的节点数。
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return ans - 1;
}
int dfs(TreeNode* root) {
if (!root) return 0;
int max_left = dfs(root->left);
int max_right = dfs(root->right);
ans = max(ans, max_left + max_right + 1);
return 1 + max(max_left, max_right);
}
private:
int ans = 1;
};
class Solution:
def __init__(self):
self.res = 0
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
if not root: return 0
self.core(root)
return self.res - 1
def core(self, root):
if not root: return 0
left_path = self.core(root.left)
right_path = self.core(root.right)
self.res = max(self.res, 1 + left_path + right_path)
return 1 + max(left_path, right_path)
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if (!root) return 0;
unordered_map<TreeNode*, int> m;
int res = -1;
m[nullptr] = 0;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
auto node = stk.top(); stk.pop();
if (m.count(node->left) && m.count(node->right)) {
m[node] = max(m[node->left], m[node->right]) + 1;
res = max(res, m[node->left] + m[node->right]);
} else {
stk.push(node);
if (node->right) stk.push(node->right);
if (node->left) stk.push(node->left);
}
}
return res;
}
};
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
if not root: return 0
m = defaultdict(int)
m[None] = 0
stk = [root]
res = -1
while len(stk) > 0:
node = stk.pop()
if node.left in m and node.right in m:
m[node] = max(m[node.left], m[node.right]) + 1
res = max(res, m[node.left] + m[node.right])
else:
stk.append(node)
if node.right: stk.append(node.right)
if node.left: stk.append(node.left)
return res
The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves ordered from left-to-right, and the reverse order of the right boundary.
分 左边界、叶子结点、右边界 来解决问题。
class Solution:
def __init__(self):
self.res = []
def is_leaf(self, root):
return not root.left and not root.right
def get_leaf(self, root):
if not root: return
if not root.left and not root.right: self.res.append(root.val)
self.get_leaf(root.left)
self.get_leaf(root.right)
def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
self.res.append(root.val)
if self.is_leaf(root): return self.res
node = root.left
while node and not self.is_leaf(node):
self.res.append(node.val)
if node.left: node = node.left
else: node = node.right
self.get_leaf(root)
node = root.right
stk = []
while node and not self.is_leaf(node):
stk.append(node.val)
if node.right: node = node.right
else: node = node.left
while len(stk) > 0: self.res.append(stk.pop())
return self.res
Time Complexity: O(n) Space Complexity: O(n)
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
这个题和<合并两个有序数组>思路类似，深度优先遍历解决问题。
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (!root1) return root2;
if (!root2) return root1;
TreeNode* root = new TreeNode(root1->val + root2->val);
root->left = mergeTrees(root1->left, root2->left);
root->right = mergeTrees(root1->right, root2->right);
return root;
}
};
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1: return root2
if not root2: return root1
node = TreeNode(root1.val + root2.val)
node.left = self.mergeTrees(root1.left, root2.left)
node.right = self.mergeTrees(root1.right, root2.right)
return node
迭代形式
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == nullptr) return t2;
if (t2 == nullptr) return t1;
auto merged = new TreeNode(t1->val + t2->val);
auto q = queue<TreeNode*>();
auto queue1 = queue<TreeNode*>();
auto queue2 = queue<TreeNode*>();
q.push(merged); queue1.push(t1); queue2.push(t2);
while (!queue1.empty() && !queue2.empty()) {
auto node = q.front(), node1 = queue1.front(), node2 = queue2.front();
q.pop(); queue1.pop(); queue2.pop();
auto left1 = node1->left, left2 = node2->left, right1 = node1->right, right2 = node2->right;
if (left1 || left2) {
if (left1 && left2) {
auto left = new TreeNode(left1->val + left2->val);
node->left = left; q.push(left); queue1.push(left1); queue2.push(left2);
} else if (left1) node->left = left1;
else if (left2) node->left = left2;
}
if (right1 || right2) {
if (right1 && right2) {
auto right = new TreeNode(right1->val + right2->val);
node->right = right; q.push(right); queue1.push(right1); queue2.push(right2);
} else if (right1) node->right = right1;
else node->right = right2;
}
}
return merged;
}
};
from collections import deque
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1: return t2
if not t2: return t1
merged = TreeNode(t1.val + t2.val)
q = deque([merged])
queue1 = deque([t1])
queue2 = deque([t2])
while queue1 and queue2:
node = q.popleft()
node1 = queue1.popleft()
node2 = queue2.popleft()
left1, left2 = node1.left, node2.left
right1, right2 = node1.right, node2.right
if left1 or left2:
if left1 and left2:
left_node = TreeNode(left1.val + left2.val)
node.left = left_node
q.append(left_node)
queue1.append(left1)
queue2.append(left2)
elif left1: node.left = left1
else: node.left = left2
if right1 or right2:
if right1 and right2:
right_node = TreeNode(right1.val + right2.val)
node.right = right_node
q.append(right_node)
queue1.append(right1)
queue2.append(right2)
elif right1: node.right = right1
else: node.right = right2
return merged
时间复杂度：O(min(m, n)) 空间复杂度：O(min(m, n))
Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value.
类似计算二叉树的直径。
class Solution:
def __init__(self):
self.res = 0
def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
self.core(root)
return self.res
def core(self, root):
if not root: return 0
left = self.core(root.left)
right = self.core(root.right)
left = left + 1 if root.left and root.left.val == root.val else 0
right = right + 1 if root.right and root.right.val == root.val else 0
self.res = max(self.res, left + right)
return max(left, right)
Time Complexity: O(n) Space Complexity: O(n)
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null。
二分遍历解决问题。
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
auto cur = root;
while (cur && cur->val != val) {
if (cur->val < val) cur = cur->right;
else cur = cur->left;
}
return cur;
}
};
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root: return None
while root and root.val != val:
if root.val > val: root = root.left
elif root.val < val: root = root.right
return root
递归形式
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (!root) return nullptr;
if (root->val == val) return root;
return searchBST(val < root->val ? root->left : root->right, val);
}
};
时间：O(log n) 空间：O(1)
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。
直接找到合适的空位，插入节点即可。
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
auto p = root;
while (p) {
if (p->val < val) {
if (p->right == nullptr) { p->right = new TreeNode(val); break; }
else p = p->right;
} else {
if (p->left == nullptr) { p->left = new TreeNode(val); break; }
else p = p->left;
}
}
return root;
}
};
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root: return TreeNode(val)
p = root
while p:
if p.val < val:
if not p.right: p.right = TreeNode(val); break
else: p = p.right
elif p.val > val:
if not p.left: p.left = TreeNode(val); break
else: p = p.left
return root
递归方法
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (root->val > val) root->left = insertIntoBST(root->left, val);
else root->right = insertIntoBST(root->right, val);
return root;
}
};
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root: return TreeNode(val)
if root.val > val: root.left = self.insertIntoBST(root.left, val)
elif root.val < val: root.right = self.insertIntoBST(root.right, val)
return root
Iteration Version: 时间：O(n) 空间：O(1) Recursion Version: 时间复杂度：O(n) 空间复杂度：O(n)
同 530
Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.
先找到每个节点的 parent，然后再通过左、右、parent 的顺序，来找到指定节点集合。
class Solution:
def __init__(self):
self.parents = {}
self.res = []
def find_parents(self, root):
if root.left: self.parents[root.left.val] = root; self.find_parents(root.left)
if root.right: self.parents[root.right.val] = root; self.find_parents(root.right)
def find_res(self, node, from_t, depth, k):
if not node: return
if depth == k: self.res.append(node.val)
if node.left != from_t: self.find_res(node.left, node, depth + 1, k)
if node.right != from_t: self.find_res(node.right, node, depth + 1, k)
if node.val in self.parents and self.parents[node.val] != from_t:
self.find_res(self.parents[node.val], node, depth + 1, k)
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
self.find_parents(root)
self.find_res(target, None, 0, k)
return self.res
Time Complexity: O(n) Space Complexity: O(n)
Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].
中序遍历解决问题。
class Solution:
def __init__(self):
self.res = 0
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
self.core(root, low, high)
return self.res
def core(self, root, low, high):
if not root: return
if low <= root.val <= high: self.res += root.val
self.core(root.left, low, high)
self.core(root.right, low, high)
Time Complexity: O(n) Space Complexity: O(n)
Given the root of a binary tree, determine if it is a complete binary tree.
层次遍历解决问题，碰到过空节点之后就不能再有空节点了。
import queue
class Solution:
def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
if not root: return True
q = queue.Queue()
q.put(root)
seen_null = False
while not q.empty():
node = q.get()
if not node: seen_null = True
elif not seen_null: q.put(node.left); q.put(node.right)
else: return False
return True
Time Complexity: O(n) Space Complexity: O(n)
Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.
class Solution:
def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
g = [[] for _ in range(n)]
for x, y in edges: g[x].append(y); g[y].append(x)
def dfs(x, fa):
cost = 0
for y in g[x]:
if y == fa: continue
y_cost = dfs(y, x)
if y_cost or hasApple[y]: cost += y_cost + 2
return cost
return dfs(0, -1)
Time Complexity: O(n) Space Complexity: O(n)
A binary tree is given such that each node contains an additional random pointer which could point to any node in the tree or null. Return a deep copy of the tree.
遍历过程中 fork，但需要记得重新构建 random 节点。
class Solution:
def copyRandomBinaryTree(self, root: 'Node') -> 'NodeCopy':
d = {}
def dfs(r):
if not r: return None
new = NodeCopy(r.val)
new.left = dfs(r.left)
new.right = dfs(r.right)
new.random = None
d[r] = new
return new
t = dfs(root)
for k, v in d.items():
if k.random in d: v.random = d[k.random]
return t
A binary tree is named Even-Odd if it meets the following conditions:
Solve the problem by level traversing.
import queue
class Solution:
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
if not root: return False
level = 0
q = queue.Queue()
q.put(root)
while not q.empty():
length = q.qsize()
last_value = -1
for i in range(length):
node = q.get()
if level % 2 == 0:
if node.val % 2 == 0: return False
if i > 0 and node.val <= last_value: return False
if level % 2 == 1:
if node.val % 2 == 1: return False
if i > 0 and node.val >= last_value: return False
last_value = node.val
if node.left: q.put(node.left)
if node.right: q.put(node.right)
level += 1
return True
Time Complexity: O(n) Space Complexity: O(n)
Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA). Each node will have a reference to its parent node.
class Solution:
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
s = set()
node = p
while node:
s.add(node)
node = node.parent
node = q
while node not in s: node = node.parent
return node
class Solution:
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
node1 = p
node2 = q
while node1 != node2:
node1 = node1.parent if node1 else q
node2 = node2.parent if node2 else p
return node1
Time Complexity: O(n) Space Complexity: O(1)
Given the root of a binary tree, return the number of nodes where the value of the node is equal to the average of the values in its subtree.
后序遍历解决问题。
class Solution:
def __init__(self):
self.res = 0
def averageOfSubtree(self, root: TreeNode) -> int:
self.core(root)
return self.res
def core(self, root):
if not root: return (0, 0)
left = self.core(root.left)
right = self.core(root.right)
if (left[0] + right[0] + root.val) // (left[1] + right[1] + 1) == root.val:
self.res += 1
return (left[0] + right[0] + root.val, left[1] + right[1] + 1)
Time Complexity: O(n) Space Complexity: O(n)
输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构) B 是 A 的子结构，即 A 中有出现和 B 相同的结构和节点值。
At first we need to find whether B is the sub structure of A and B's root is anchored to A's root. If it is yes, just return True. If it is no, we need to do the same thing to A's left and right recursively.
class Solution {
public:
bool is_sub(TreeNode* A, TreeNode* B) {
if (!B) return true;
if (!A) return false;
if (A->val != B->val) return false;
return is_sub(A->left, B->left) && is_sub(A->right, B->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (A && B) {
if (is_sub(A, B)) return true;
return isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
return false;
}
};
class Solution:
def is_sub(self, A, B):
if not B: return True
if not A: return False
if A.val != B.val: return False
return self.is_sub(A.left, B.left) and self.is_sub(A.right, B.right)
def isSubStructure(self, A: Optional[TreeNode], B: Optional[TreeNode]) -> bool:
if A and B:
return self.is_sub(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)
return False
时间复杂度：O(MN) 空间复杂度：O(M)
请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。
BST 后序遍历序列的特点是先左子树序列，再右子树序列，最后是根节点。左子树序列的所有节点都小于根节点，右子树序列的所有节点都大于根节点。根据这个特性我们可以通过中序遍历来解决问题。
class Solution {
public:
bool verifyTreeOrder(vector<int>& postorder) {
return dfs(postorder, 0, postorder.size() - 1);
}
bool dfs(vector<int>& postorder, int i, int j) {
if (i >= j) return true;
int p = i;
while (postorder[p] < postorder[j]) ++p;
int m = p;
while (postorder[p] > postorder[j]) ++p;
return p == j && dfs(postorder, i, m - 1) && dfs(postorder, m, j - 1);
}
};
class Solution:
def verifyTreeOrder(self, postorder: List[int]) -> bool:
if len(postorder) <= 2: return True
return self.core(postorder, 0, len(postorder) - 1)
def core(self, postorder, left, right):
if left >= right: return True
root_val = postorder[right]
idx = left
for i in range(left, right + 1):
if postorder[i] >= root_val: idx = i; break
for i in range(idx, right + 1):
if postorder[i] <= root_val: break
return i == right and self.core(postorder, left, idx - 1) and self.core(postorder, idx, right - 1)
class Solution {
public:
bool verifyTreeOrder(vector<int>& postorder) {
stack<int> stk;
int parent = INT_MAX;
for (int i = postorder.size() - 1; i >= 0; --i) {
int cur = postorder[i];
while (!stk.empty() && stk.top() > cur) { parent = stk.top(); stk.pop(); }
if (cur > parent) return false;
stk.push(cur);
}
return true;
}
};
变换前：BST 变换后：双向循环链表
Maintain pre and head during in-order traversal of the BST. We need to connect the head and tail node of the linked list after traversal.
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if (!root) return nullptr;
core(root);
head->left = pre;
pre->right = head;
return head;
}
void core(Node* cur) {
if (!cur) return;
core(cur->left);
if (pre) pre->right = cur;
else head = cur;
cur->left = pre;
pre = cur;
core(cur->right);
}
private:
Node* pre;
Node* head;
};
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
head = None
pre = None
if not root: return head
stk = []
while root or len(stk) > 0:
while root: stk.append(root); root = root.left
node = stk.pop()
if pre: pre.right = node
else: head = node
node.left = pre
pre = node
root = node.right
head.left = pre
pre.right = head
return head
时间：O(n) 空间：O(n)
给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
class Solution {
public:
int depth(TreeNode* root) {
if (!root) return 0;
int left_depth = depth(root->left);
int right_depth = depth(root->right);
return 1 + max(left_depth, right_depth);
}
bool isBalanced(TreeNode* root) {
if (!root) return true;
int left_depth = depth(root->left);
int right_depth = depth(root->right);
if (abs(left_depth - right_depth) >= 2) return false;
return isBalanced(root->left) && isBalanced(root->right);
}
};
时间复杂度：O(n^2) 空间复杂度：O(n)
class Solution {
public:
int depth(TreeNode* root) {
if (!root) return 1;
int left_depth = depth(root->left);
int right_depth = depth(root->right);
if (left_depth == -1 || right_depth == -1 || abs(left_depth - right_depth) >= 2) return -1;
return 1 + max(left_depth, right_depth);
}
bool isBalanced(TreeNode* root) {
return depth(root) >= 0;
}
};
class Solution:
def depth(self, root):
if not root: return 1
left_d = self.depth(root.left)
right_d = self.depth(root.right)
if left_d == -1 or right_d == -1 or abs(left_d - right_d) >= 2: return -1
return 1 + max(left_d, right_d)
def isBalanced(self, root: Optional[TreeNode]) -> bool:
return self.depth(root) >= 0
时间复杂度：O(n) 空间复杂度：O(n)
给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。
最复杂的情况在于如果一个节点 node, 它是其父节点的右节点而且没有右子树，那么就向父节点回溯，直到找到一个节点 node, 如果它是它的父节点的左子节点，那么 node 的父节点就是我们要找到的 node 的下一个节点。
class Solution {
public:
TreeNode* nextNode(TreeNode* root) {
if (!root) return nullptr;
TreeNode* next_node = root->right;
if (next_node) {
while (next_node->left) next_node = next_node->left;
} else {
auto parent_node = root->parent;
while (parent_node && root == parent_node->right) {
root = parent_node;
parent_node = parent_node->parent;
}
next_node = parent_node;
}
return next_node;
}
};
时间复杂度：O(n) 空间复杂度：O(1)
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online