本文总结了二叉树的各类经典问题及解法，并进行了分类，代码片段中题目描述注释部分中紧接着题目后面方括号内的数字为该题在 LeetCode 题库中的编号，算法的说明随同附带在代码片段的注释之中，另外不做额外解释。二叉树最经典的问题便是遍历与重建，具体可参考另一篇文章 Non-recursive traversal and reconstruction of binary tree，此不赘述。
本文涉及的所有题目及实现代码下载链接为：http://xule.ren/wp-content/uploads/2018/03/LeetCode_tree.zip
所有题目默认的二叉树结点的定义如下，具体题目涉及不同的树结点定义时会在题目注释中特别指明
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
Levelorder Traversal
所有层序遍历相关的题目都可以采用如下模板，不同题目的差别一般都位于模板中的注释处
void levelOrder(TreeNode *root)
{
if (root == NULL)
return;
/* do something */
std::queue<TreeNode*> Q;
Q.push(root);
while (!Q.empty())
{
size_t sz = Q.size();
/* do something */
while (sz-- > 0)
{
TreeNode *p = Q.front();
Q.pop();
/* do something */
if (p->left != NULL)
Q.push(p->left);
if (p->right != NULL)
Q.push(p->right);
}
/* do something */
}
}
LeetCode 上有以下七道与层序遍历相关的题目
第 1 题：Binary Tree Level Order Traversal
/**
* 1. Binary Tree Level Order Traversal [102]
*
* Given a binary tree, return the level order traversal of its nodes' values.
* (ie, from left to right, level by level).
* @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]
* ]
* @endexample
*/
std::vector<std::vector<int> > levelOrder(TreeNode *root)
{
std::vector<std::vector<int> > res;
if (root == NULL)
return res;
std::vector<int> level;
std::queue<TreeNode*> Q;
TreeNode *p = NULL;
Q.push(root);
while (!Q.empty())
{
size_t sz = Q.size();
while (sz-- > 0)
{
p = Q.front();
Q.pop();
level.push_back(p->val);
if (p->left != NULL)
Q.push(p->left);
if (p->right != NULL)
Q.push(p->right);
}
res.push_back(level);
level.clear();
}
return res;
}
第 2 题：Binary Tree Level Order Traversal II
/**
* 2. Binary Tree Level Order Traversal II [107]
*
* Given a binary tree, return the bottom-up level order traversal of its nodes' values.
* (ie, from left to right, level by level from leaf to root).
* @example
* Given binary tree [3,9,20,null,null,15,7],
* 3
* / \
* 9 20
* / \
* 15 7
* return its bottom-up level order traversal as:
* [
* [15,7],
* [9,20],
* [3]
* ]
* @endexample
*/
std::vector<std::vector<int> > levelOrderBottom(TreeNode *root)
{
if (root == NULL)
return std::vector<std::vector<int> >();
int depth = maxDepth(root);
std::vector<std::vector<int> > res(depth, std::vector<int>());
std::queue<TreeNode*> Q;
TreeNode *p = NULL;
Q.push(root);
while (!Q.empty())
{
size_t sz = Q.size();
--depth;
while (sz-- > 0)
{
p = Q.front();
Q.pop();
res[depth].push_back(p->val);
if (p->left != NULL)
Q.push(p->left);
if (p->right != NULL)
Q.push(p->right);
}
}
return res;
}
同第 1 题几乎一样，只是事先取得了树的深度以便对存储结果的 vector 预分配大小以避免扩容时拷贝导致的开销。
第 3 题：Binary Tree Zigzag Level Order Traversal
/**
* 3. Binary Tree Zigzag Level Order Traversal [103]
*
* 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).
* @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]
* ]
* @endexample
*/
std::vector<std::vector<int> > zigzagLevelOrder(TreeNode *root)
{
std::vector<std::vector<int> > res;
if (root == NULL)
return res;
std::vector<int> level;
std::deque<TreeNode*> Q;
TreeNode *p = NULL;
Q.push_back(root);
bool iszig = true;
while (!Q.empty())
{
size_t sz = Q.size();
iszig = iszig == false;
while (sz-- > 0)
{
if (iszig) // pop_front, push_back, right then left
{
p = Q.front();
Q.pop_front();
level.push_back(p->val);
if (p->right)
Q.push_back(p->right);
if (p->left)
Q.push_back(p->left);
}
else // pop_back, push_front, left then right
{
p = Q.back();
Q.pop_back();
level.push_back(p->val);
if (p->left)
Q.push_front(p->left);
if (p->right)
Q.push_front(p->right);
}
}
res.push_back(level);
level.clear();
}
return res;
}
采用双端队列而不是普通队列使得某层的树结点既可以按从左往右的顺序入队列，也可以从右往左的顺序入队列。
第 4 题：Find Largest Value in Each Tree Row
/**
* 4. Find Largest Value in Each Tree Row [515]
*
* You need to find the largest value in each row of a binary tree.
* @example
* Input:
* 1
* / \
* 3 2
* / \ \
* 5 3 9
* Output: [1, 3, 9]
* @endexample
*/
std::vector<int> largestValues(TreeNode *root)
{
std::vector<int> res;
if (root == NULL)
return res;
std::queue<TreeNode*> Q;
TreeNode *p = NULL;
Q.push(root);
while (!Q.empty())
{
size_t sz = Q.size();
int rowMax = -2147483648;
while (sz-- > 0)
{
p = Q.front();
Q.pop();
if (rowMax < p->val)
rowMax = p->val;
if (p->left != NULL)
Q.push(p->left);
if (p->right != NULL)
Q.push(p->right);
}
res.push_back(rowMax);
}
return res;
}
第 5 题：Average of Levels in Binary Tree
/**
* 5. Average of Levels in Binary Tree [637]
*
* Given a non-empty binary tree, return the average value of
* the nodes on each level in the form of an array.
* @example
* Input:
* 3
* / \
* 9 20
* / \
* 15 7
* Output: [3, 14.5, 11]
* Explanation:
* The average value of nodes on level 0 is 3, on level 1 is 14.5,
* and on level 2 is 11. Hence return [3, 14.5, 11].
* @endexample
* Note:
* The range of node's value is in the range of 32-bit signed integer.
*/
std::vector<double> averageOfLevels(TreeNode *root)
{
std::vector<double> res;
if (root == NULL)
return res;
double levelSum = 0.0;
std::queue<TreeNode*> Q;
TreeNode *p = NULL;
Q.push(root);
while (!Q.empty())
{
int sz = static_cast<int>(Q.size());
for (int i = 0; i < sz; ++i)
{
p = Q.front();
Q.pop();
levelSum += p->val;
if (p->left != NULL)
Q.push(p->left);
if (p->right != NULL)
Q.push(p->right);
}
res.push_back(levelSum / sz);
levelSum = 0.0;
}
return res;
}
同第 4 题一样，套用层序遍历的模板即可。
第 6 题：Add One Row to Tree
/**
* 6. Add One Row to Tree [623]
*
* Given the root of a binary tree, then value v and depth d,
* you need to add a row of nodes with value v at the given
* depth d. The root node is at depth 1.
* The adding rule is: given a positive integer depth d, for each
* NOT null tree nodes N in depth d-1, create two tree nodes with
* value v as N's left subtree root and right subtree root.
* And N's original left subtree should be the left subtree of
* the new left subtree root, its original right subtree should be
* the right subtree of the new right subtree root. If depth d is
* 1 that means there is no depth d-1 at all, then create a tree
* node with value v as the new root of the whole original tree,
* and the original tree is the new root's left subtree.
* @example
* Input:
* A binary tree as following:
* 4
* / \
* 2 6
* / \ /
* 3 1 5
* v = 1
* d = 2
* Output:
* 4
* / \
* 1 1
* / \
* 2 6
* / \ /
* 3 1 5
* @endexample
* @example
* Input:
* A binary tree as following:
* 4
* /
* 2
* / \
* 3 1
* v = 1
* d = 3
* Output:
* 4
* /
* 2
* / \
* 1 1
* / \
* 3 1
* @endexample
* Note:
* 1. The given d is in range [1, maximum depth of the given tree + 1].
* 2. The given binary tree has at least one tree node.
*/
TreeNode* addOneRow(TreeNode *root, int v, int d)
{
if (d == 1)
{
TreeNode *newRoot = new TreeNode(v);
newRoot->left = root;
return newRoot;
}
int depth = 0;
std::queue<TreeNode*> Q;
TreeNode *p = NULL;
Q.push(root);
while (!Q.empty())
{
size_t sz = Q.size();
if (++depth == d-1)
{
while (sz-- > 0)
{
p = Q.front();
Q.pop();
TreeNode *q = p->left;
p->left = new TreeNode(v);
p->left->left = q;
q = p->right;
p->right = new TreeNode(v);
p->right->right = q;
}
break;
}
while (sz-- > 0)
{
p = Q.front();
Q.pop();
if (p->left != NULL)
Q.push(p->left);
if (p->right != NULL)
Q.push(p->right);
}
}
return root;
}
对 d 等于 1 的情况进行单独处理即可，仍然是套用模板。
第 7 题：Maximum Width of Binary Tree
/**
* 7. Maximum Width of Binary Tree [662]
*
* 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
* 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).
* @endexample
* @example
* Input:
* 1
* /
* 3
* / \
* 5 3
* Output: 2
* Explanation: The maximum width existing in the third level with
* the length 2 (5,3).
* @endexample
* @example
* Input:
* 1
* / \
* 3 2
* /
* 5
* Output: 2
* Explanation: The maximum width existing in the second level with
* the length 2 (3,2).
* @endexample
* @example
* Input:
* 1
* / \
* 3 2
* / \
* 5 9
* / \
* 6 7
* Output: 8
* Explanation:The maximum width existing in the fourth level with
* the length 8 (6,null,null,null,null,null,null,7).
* @endexample
* Note:
* Answer will in the range of 32-bit signed integer.
*/
int widthOfBinaryTree(TreeNode *root)
{
if (root == NULL)
return 0;
int maxWidth = 0;
std::queue<std::pair<TreeNode*, int> > Q;
Q.push(std::pair<TreeNode*, int>(root, 1));
while (!Q.empty())
{
size_t sz = Q.size();
int leftIdx = Q.front().second, rightIdx = leftIdx;
for (size_t i = 0; i < sz; ++i)
{
TreeNode *p = Q.front().first;
rightIdx = Q.front().second;
Q.pop();
if (p->left != NULL)
Q.push(std::pair<TreeNode*, int>(p->left, 2*rightIdx));
if (p->right != NULL)
Q.push(std::pair<TreeNode*, int>(p->right, 2*rightIdx+1));
}
if (maxWidth < rightIdx - leftIdx + 1)
maxWidth = rightIdx - leftIdx + 1;
}
return maxWidth;
}
本题的诀窍是假定给定的树在一棵完全二叉树，求各个树结点在此假想的完全二叉树中的编号，根结点编号为 1，对于完全二叉树中任何一个编号为 x 的树结点，其左孩子编号为 2x，右孩子编号为 2x + 1，每一层的宽度就是最右侧结点的编号减去最左侧结点的编号加 1。
Preorder Traversal
此类题大多采用先序遍历的递归版本实现，LeetCode 上有以下八道与先序遍历相关的题目
第 1 题：Symmetric Tree
/**
* 1. Symmetric Tree [101]
*
* Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
* @example
* This binary tree [1,2,2,3,4,4,3] is symmetric:
* 1
* / \
* 2 2
* / \ / \
* 3 4 4 3
* @endexample
* @example
* But the following [1,2,2,null,3,null,3] is not:
* 1
* / \
* 2 2
* \ \
* 3 3
* @endexample
* Note:
* Bonus points if you could solve it both recursively and iteratively.
*/
class Solution
{
public:
bool isSymmetric(TreeNode *root)
{
return root == NULL || isSymmetric(root->left, root->right);
}
private:
bool isSymmetric(TreeNode *left, TreeNode *right)
{
if (left == NULL && right == NULL)
return true;
return left != NULL && right != NULL && left->val == right->val ? isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left) : false;
}
};
在递归调用中把左孩子的左子树与右孩子的右子树进行比较，把左孩子的右子树与右孩子的左子树进行比较。
第 2 题：Binary Tree Right Side View
/**
* 2. Binary Tree Right Side View [199]
*
* Given a binary tree, imagine yourself standing on the right side of it,
* return the values of the nodes you can see ordered from top to bottom.
* @example
* Given the following binary tree,
* 1 <---
* / \
* 2 3 <---
* \ \
* 5 4 <---
* You should return [1, 3, 4].
* @endexample
*/
class Solution
{
public:
std::vector<int> rightSideView(TreeNode *root)
{
std::vector<int> res;
preorder(root, 0, res);
return res;
}
private:
void preorder(TreeNode *root, size_t lv, std::vector<int>& res)
{
if (root == NULL)
return;
if (lv >= res.size())
res.push_back(root->val);
preorder(root->right, lv+1, res);
preorder(root->left, lv+1, res);
}
};
此题并非严格的先序遍历但采用了先序遍历的思想，若题目要求 Left Side View 则为先序遍历。因为右子树先被递归调用，因此首次 lv == res.size() 的时候，此刻的 root 必然是这一层树结点中最右侧的结点。
第 3 题：Count Complete Tree Nodes
/**
* 3. Count Complete Tree Nodes [222]
*
* Given a complete binary tree, count the number of nodes.
* Definition of a complete binary tree from Wikipedia:
* In a complete binary tree every level, except possibly the last, is completely
* filled, and all nodes in the last level are as far left as possible.
* It can have between 1 and 2h nodes inclusive at the last level h.
*/
int countNodes(TreeNode *root)
{
if (root == NULL)
return 0;
TreeNode *l = root, *r = root;
int height = 0;
while (r != NULL)
{
l = l->left;
r = r->right;
++height;
}
return l == NULL ? (1 << height) - 1 : 1 + countNodes(root->left) + countNodes(root->right);
}
当 l 和 r 同时为 NULL 时表明 root 为某棵满二叉子树的根结点，完全二叉树可以递归地拆分成几棵满二叉树，只要找到这几棵满二叉树的根结点即可，由于递归的过程沿树向下，对某棵子树的测试需要 h 的时间（h 为该子树的树高），在最坏的情况下，刚好最后一层仅有最左侧的一个结点，递归调用的次数为整棵树的树高 log n，则总的时间复杂度为 O(log^2 n)。
第 4 题：Invert Binary Tree
/**
* 4. Invert Binary Tree [226]
*
* Invert a binary tree.
* @example
* 4
* / \
* 2 7
* / \ / \
* 1 3 6 9
*
* 4
* / \
* 7 2
* / \ / \
* 9 6 3 1
* @endexample
*/
TreeNode* invertTree(TreeNode *root)
{
if (root == NULL)
return NULL;
TreeNode *prevLeft = invertTree(root->left);
root->left = invertTree(root->right);
root->right = prevLeft;
return root;
}
第 5 题：Second Minimum Node In a Binary Tree
/**
* 5. Second Minimum Node In a Binary Tree [671]
*
* Given a non-empty special binary tree consisting of nodes with
* the non-negative value, where each node in this tree has exactly
* two or zero sub-node. If the node has two sub-nodes, then this
* node's value is the smaller value among its two sub-nodes.
* Given such a binary tree, you need to output the second minimum
* value in the set made of all the nodes' value in the whole tree.
* If no such second minimum value exists, output -1 instead.
* @example
* Input:
* 2
* / \
* 2 5
* / \
* 5 7
* Output: 5
* Explanation: The smallest value is 2, the second smallest value is 5.
* @endexample
* @example
* Input:
* 2
* / \
* 2 2
* Output: -1
* Explanation: The smallest value is 2, but there isn't any
* second smallest value.
* @endexample
*/
class Solution
{
public:
int findSecondMinimumValue(TreeNode *root)
{
if (root == NULL || root->left == NULL && root->right == NULL)
return -1;
int res = 2147483647;
bool hasSecondMin = false;
minimumValue(root, res, root->val, hasSecondMin);
return hasSecondMin ? res : -1;
}
private:
void minimumValue(TreeNode *node, int& secondMin, int rootVal, bool& flag)
{
if (rootVal < node->val)
{
flag = true;
if (secondMin > node->val)
secondMin = node->val;
}
if (node->left != NULL && node->left->val <= secondMin)
minimumValue(node->left, secondMin, rootVal, flag);
if (node->right != NULL && node->right->val <= secondMin)
minimumValue(node->right, secondMin, rootVal, flag);
}
};
为了防止树中第二小的值恰好就是 2147483647 的值，此时若省去 flag，把 if 语句写成 if (rootVal < node->val && secondMin > node->val) secondMin = node->val 然后在返回语句中检测 res 是否小于 2147483647 来判断是否存在第二小的值就行不通，因此需要一个额外的 flag 以指示树中是否存在第二小的值。
第 6 题：Same Tree
/**
* 6. Same Tree [100]
*
* Given two binary trees, write a function to check if they are the same or not.
* Two binary trees are considered the same if they are structurally identical
* and the nodes have the same value.
* @example
* Input: 1 1
* / \ / \
* 2 3 2 3
* [1,2,3], [1,2,3]
* Output: true
* @endexample
* @example
* Input: 1 1
* / \
* 2 2
* [1,2], [1,null,2]
* Output: false
* @endexample
* @example
* Input: 1 1
* / \ / \
* 2 1 1 2
* [1,2,1], [1,1,2]
* Output: false
* @endexample
*/
/**
* 1)
* If one of the node is NULL then return the equality result of p an q.
* This boils down to if both are NULL then return true,
* but if one of them is NULL but not the other one then return false
* 2)
* At this point both root nodes represent valid pointers.
* Return true if the root nodes have same value and
* the left tree of the roots are same (recursion)
* and the right tree of the roots are same (recursion).
* Otherwise return false.
*/
bool isSameTree(TreeNode *p, TreeNode *q)
{
if (p == NULL || q == NULL)
return p == q;
return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
第 7 题：Subtree of Another Tree
/**
* 7. Subtree of Another Tree [572]
*
* Given two non-empty binary trees s and t, check whether tree t has exactly
* the same structure and node values with a subtree of s. A subtree of s is
* a tree consists of a node in s and all of this node's descendants.
* The tree s could also be considered as a subtree of itself.
* @example
* Given tree s:
* 3
* / \
* 4 5
* / \
* 1 2
* Given tree t:
* 4
* / \
* 1 2
* Return true, because t has the same structure and node values with a subtree of s.
* @endexample
* @example
* Given tree s:
* 3
* / \
* 4 5
* / \
* 1 2
* /
* 0
* Given tree t:
* 4
* / \
* 1 2
* Return false.
* @endexample
*/
class Solution
{
public:
bool isSubtree(TreeNode *s, TreeNode *t)
{
return isSame(s, t) || (s->left != NULL && isSubtree(s->left, t)) || (s->right != NULL && isSubtree(s->right, t));
}
private:
bool isSame(TreeNode *s, TreeNode *t)
{
return s->val == t->val
&& ((s->left == NULL && t->left == NULL) || (s->left != NULL && t->left != NULL && isSame(s->left, t->left)))
&& ((s->right == NULL && t->right == NULL) || (s->right != NULL && t->right != NULL && isSame(s->right, t->right)));
}
};
在最好的情况下，两棵树完全相同，此时 isSubtree() 不需要进行递归调用，时间复杂度为 O(n)；在最坏的情况下，一棵树尺寸和另一颗树差不多且不是另一颗树的子树，此时固定其中一棵树作为被比较的树，另一棵树不断调整根结点在固定的树中的位置去与之相比，由于在比较的过程中起始比较位置在固定的树中不断下降，在 isSame() 中需要被比较的树结点的数目也不断减少（呈线性减少，因为高度线性下降），最终只需比较一次即可退出 isSame()，即不需递归调用 isSame()，于是总的时间复杂度大约是 O(n^2)。
第 8 题：Merge Two Binary Trees
/**
* 8. Merge Two Binary Trees [617]
*
* Given two binary trees and imagine that when you put one of them to cover
* the other, some nodes of the two trees are overlapped while the others are not.
* You need to merge them into a new binary tree. The merge rule is that if
* two nodes overlap, then sum node values up as the new value of the merged
* node. Otherwise, the NOT null node will be used as the node of new tree.
* @example
* Input:
* Tree 1 Tree 2
* 1 2
* / \ / \
* 3 2 1 3
* / \ \
* 5 4 7
* Output:
* Merged tree:
* 3
* / \
* 4 5
* / \ \
* 5 4 7
* @endexample
* Note:
* The merging process must start from the root nodes of both trees.
*/
TreeNode* mergeTrees(TreeNode *t1, TreeNode *t2)
{
if (t1 == NULL || t2 == NULL)
return t1 == NULL ? t2 : t1;
TreeNode *root = new TreeNode(t1->val + t2->val);
root->left = mergeTrees(t1->left, t2->left);
root->right = mergeTrees(t1->right, t2->right);
return root;
}
创建新结点而不是使用其中一棵树现成的结点，这样不会造成销毁树时谁该负责内存释放的问题。
Postorder Traversal
此类题大多采用后序遍历的递归版本实现，后序遍历的递归算法大多都是 O(n) 的，因为子树的结点不会被重复访问。先序遍历采用的是自顶向下的思想，后序遍历采用的是自底向上的思想。LeetCode 上有以下七道与后序遍历相关的题目
第 1 题：Maximum Depth of Binary Tree
/**
* 1. Maximum Depth of Binary Tree [104]
*
* 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.
*/
int maxDepth(TreeNode *root)
{
return root != NULL ? std::max(maxDepth(root->left), maxDepth(root->right)) + 1 : 0;
}
第 2 题：Minimum Depth of Binary Tree
/**
* 2. Minimum Depth of Binary Tree [111]
*
* Given a binary tree, find its minimum depth.
* The minimum depth is the number of nodes along the shortest path
* from the root node down to the nearest leaf node.
*/
int minDepth(TreeNode *root)
{
if (root == NULL)
return 0;
if (root->left == NULL)
return minDepth(root->right) + 1;
if (root->right == NULL)
return minDepth(root->left) + 1;
return std::min(minDepth(root->left), minDepth(root->right)) + 1;
}
注意当左子树或右子树为空的时候，需要返回另一棵子树的高度，因为最小深度的叶子结点可能就在另一侧的子树中。
第 3 题：Balanced Binary Tree
/**
* 3. Balanced Binary Tree [110]
*
* Given a binary tree, determine if it is height-balanced.
* For this problem, a height-balanced binary tree is defined as a binary tree
* in which the depth of the two subtrees of every node never differ by more than 1.
*/
/**
* Instead of calling depth() explicitly for each child node, we return the height of the
* current node in DFS recursion. When the sub tree of the current node (inclusive) is
* balanced, the function dfsHeight() returns a non-negative value as the height.
* Otherwise -1 is returned. According to the leftHeight and rightHeight of the two children,
* the parent node could check if the sub tree is balanced, and decides its return value.
*/
class Solution
{
public:
bool isBalanced(TreeNode *root)
{
return dfsHeight(root) != -1;
}
private:
int dfsHeight(TreeNode *root)
{
if (root == NULL)
return 0;
int leftHeight = dfsHeight(root->left);
if (leftHeight == -1)
return -1;
int rightHeight = dfsHeight(root->right);
if (rightHeight == -1)
return -1;
if (leftHeight - rightHeight > 1 || rightHeight - leftHeight > 1)
return -1;
return std::max(leftHeight, rightHeight) + 1;
}
};
采用 -1 这个不可能是高度的值作为指示值，以表示某个树结点处不满足平衡条件，以便尽早退出递归避免接下去无用的检测。
第 4 题：Find Bottom Left Tree Value
/**
* 4. Find Bottom Left Tree Value [513]
*
* Given a binary tree, find the leftmost value in the last row of the tree.
* @example
* Input:
* 2
* / \
* 1 3
* Output:
* 1
* @endexample
* @example
* Input:
* 1
* / \
* 2 3
* / / \
* 4 5 6
* /
* 7
* Output:
* 7
* @endexample
* Note:
* You may assume the tree (i.e., the given root node) is not NULL.
*/
class Solution
{
public:
int findBottomLeftValue(TreeNode *root)
{
int maxDepth = 0, res = root->val;
findBottomLeftValue(root, 0, maxDepth, res);
return res;
}
private:
void findBottomLeftValue(TreeNode *root, int depth, int& maxDepth, int& res)
{
if (root == NULL)
return;
findBottomLeftValue(root->left, depth+1, maxDepth, res);
findBottomLeftValue(root->right, depth+1, maxDepth, res);
if (maxDepth < depth)
{
maxDepth = depth;
res = root->val;
}
}
};
同 Binary Tree Right Side View 那题的思路类似，每一层中只有最左侧的结点是首次到达该层时被访问的，于是 maxDepth 就被置为该层的深度以使得后续该层的其他结点被访问时不会对 res 重新赋值，该题也可以采用先序遍历的方式来实现。
第 5 题：Binary Tree Tilt
/**
* 5. Binary Tree Tilt [563]
*
* Given a binary tree, return the tilt of the whole tree.
* The tilt of a tree node is defined as the absolute difference
* between the sum of all left subtree node values and the sum of
* all right subtree node values. Null node has tilt 0.
* The tilt of the whole tree is defined as the sum of all nodes' tilt
* @example
* Input:
* 1
* / \
* 2 3
* Output: 1
* Explanation:
* Tilt of node 2 : 0
* Tilt of node 3 : 0
* Tilt of node 1 : |2-3| = 1
* Tilt of binary tree : 0 + 0 + 1 = 1
* @endexample
* Note:
* 1. The sum of node values in any subtree won't exceed the range
* of 32-bit integer.
* 2. All the tilt values won't exceed the range of 32-bit integer.
*/
class Solution
{
public:
int findTilt(TreeNode *root)
{
if (root == NULL || root->left == NULL && root->right == NULL)
return 0;
int wholeTilt = 0;
calcTilt(root, wholeTilt);
return wholeTilt;
}
private:
int calcTilt(TreeNode *root, int& whole)
{
int leftSum = root->left != NULL ? calcTilt(root->left, whole) : 0;
int rightSum = root->right != NULL ? calcTilt(root->right, whole) : 0;
whole += leftSum >= rightSum ? leftSum - rightSum : rightSum - leftSum;
return root->val + leftSum + rightSum;
}
};
父结点的处理依赖于子结点的处理，后序遍历便是理所当然的选择。
第 6 题：Sum of Left Leaves
/**
* 6. Sum of Left Leaves [404]
*
* Find the sum of all left leaves in a given binary tree.
* @example
* 3
* / \
* 9 20
* / \
* 15 7
* There are two left leaves in the binary tree, with
* values 9 and 15 respectively. Return 24.
* @endexample
*/
int sumOfLeftLeaves(TreeNode *root)
{
if (root == NULL)
return 0;
int rightSum = root->right != NULL ? sumOfLeftLeaves(root->right) : 0;
if (root->left != NULL && root->left->left == NULL && root->left->right == NULL)
return root->left->val + rightSum;
else
return sumOfLeftLeaves(root->left) + rightSum;
}
当左子树为叶子结点时停止左子树的递归调用。
第 7 题：Most Frequent Subtree Sum
/**
* 7. Most Frequent Subtree Sum [508]
*
* Given the root of a tree, you are asked to find the most frequent subtree sum.
* The subtree sum of a node is defined as the sum of all the node values formed
* by the subtree rooted at that node (including the node itself). So what is the
* most frequent subtree sum value? If there is a tie, return all the values with
* the highest frequency in any order.
* @example
* Input:
* 5
* / \
* 2 -3
* return [2, -3, 4], since all the values happen only once, return all of
* them in any order.
* @endexample
* @example
* Input:
* 5
* / \
* 2 -5
* return [2], since 2 happens twice, however -5 only occur once.
* @endexample
* Note:
* You may assume the sum of values in any subtree is in the range of 32-bit signed integer.
*/
class Solution
{
public:
std::vector<int> findFrequentTreeSum(TreeNode *root)
{
std::vector<int> res;
if (root == NULL)
return res;
int maxFrequency = 0;
std::unordered_map<int, int> subsumFrequency;
subtreeSum(root, maxFrequency, subsumFrequency);
std::unordered_map<int, int>::iterator it = subsumFrequency.begin();
for (; it != subsumFrequency.end(); ++it)
if (it->second == maxFrequency)
res.push_back(it->first);
return res;
}
private:
int subtreeSum(TreeNode *root, int& maxF, std::unordered_map<int, int>& mp)
{
int curSum = root->val;
curSum += root->left != NULL ? subtreeSum(root->left, maxF, mp) : 0;
curSum += root->right != NULL ? subtreeSum(root->right, maxF, mp) : 0;
int curF = ++mp[curSum];
if (maxF < curF)
maxF = curF;
return curSum;
}
};
涉及到频数统计的题目，大多都是采用哈希表。
Binary Tree Path
树路径相关的题目也是比较常见的，涉及从根结点到叶子结点的路径类型的题目大多采用先序遍历，如果路径可以从左子树到右子树，不一定沿着树高的方向，且不一定需要通过根结点，这种类型的题目大多采用后序遍历。LeetCode 上有以下八道与树路径相关的题目
第 1 题：Binary Tree Paths
/**
* 1. Binary Tree Paths [257]
*
* Given a binary tree, return all root-to-leaf paths.
* @example
* Given the following binary tree:
* 1
* / \
* -2 3
* \
* 5
* All root-to-leaf paths are: ["1->-2->5", "1->3"]
* @endexample
*/
class Solution
{
public:
std::vector<std::string> binaryTreePaths(TreeNode *root)
{
std::vector<std::string> paths;
if (root == NULL)
return paths;
std::string path;
preOrder(root, path, paths);
return paths;
}
private:
void preOrder(TreeNode *root, std::string& path, std::vector<std::string>& paths)
{
std::string s(std::to_string(root->val));
path.append(s);
if (root->left == NULL && root->right == NULL)
paths.push_back(path);
if (root->left != NULL)
{
path.append("->");
preOrder(root->left, path, paths);
path.pop_back();
path.pop_back();
}
if (root->right != NULL)
{
path.append("->");
preOrder(root->right, path, paths);
path.pop_back();
path.pop_back();
}
size_t newEnd = path.size() - s.size();
path.erase(path.begin()+newEnd, path.end());
}
};
第 2 题：Sum Root to Leaf Numbers
/**
* 2. Sum Root to Leaf Numbers [129]
*
* Given a binary tree containing digits from 0-9 only,
* each root-to-leaf path could represent a number.
* An example is the root-to-leaf path 1->2->3 which represents the number 123.
* Find the total sum of all root-to-leaf numbers.
* @example
* 1
* / \
* 2 3
* The root-to-leaf path 1->2 represents the number 12.
* The root-to-leaf path 1->3 represents the number 13.
* Return the sum = 12 + 13 = 25.
* @endexample
*/
class Solution
{
public:
int sumNumbers(TreeNode *root)
{
int curVal = 0, sum = 0;
preOrder(root, curVal, sum);
return sum;
}
private:
void preOrder(TreeNode *root, int& curVal, int& curSum)
{
if (root != NULL)
{
curVal *= 10;
curVal += root->val;
if (root->left != NULL || root->right != NULL)
{
preOrder(root->left, curVal, curSum);
preOrder(root->right, curVal, curSum);
}
else
curSum += curVal;
curVal /= 10;
}
}
};
典型的先序遍历题型。
第 3 题：Path Sum
/**
* 3. Path Sum [112]
*
* Given a binary tree and a sum, determine if the tree has a root-to-leaf path
* such that adding up all the values along the path equals the given sum.
* @example
* Given the below binary tree and sum = 22,
* 5
* / \
* 4 8
* / / \
* 11 13 4
* / \ \
* 7 2 1
* return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
* @endexample
*/
bool hasPathSum(TreeNode *root, int sum)
{
if (root == NULL)
return false;
if (root->left == NULL && root->right == NULL && root->val == sum)
return true;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
第 4 题：Path Sum II
/**
* 4. Path Sum II [113]
*
* Given a binary tree and a sum, find all root-to-leaf paths
* where each path's sum equals the given sum.
* @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]
* ]
* @endexample
*/
class Solution
{
public:
std::vector<std::vector<int> > pathSum(TreeNode *root, int sum)
{
std::vector<std::vector<int> > paths;
std::vector<int> path;
int curSum = 0, target = sum;
preOrder(root, curSum, target, path, paths);
return paths;
}
private:
void preOrder(TreeNode *root, int& curSum, int& target, std::vector<int>& path, std::vector<std::vector<int> >& paths)
{
if (root != NULL)
{
path.push_back(root->val);
curSum += root->val;
if (root->left == NULL && root->right == NULL && curSum == target)
paths.push_back(path);
preOrder(root->left, curSum, target, path, paths);
preOrder(root->right, curSum, target, path, paths);
curSum -= root->val;
path.pop_back();
}
}
};
第 5 题：Path Sum III
/**
* 5. Path Sum III [437]
*
* 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
* @endexample
*/
/**
* The interesting part of this solution is that the prefix is counted from
* the top(root) to the bottom(leaves), and the result of total count is
* calculated from the bottom to the top.
* 1. The prefix stores the sum from the root to the current node in the recursion;
* 2. The map stores <prefix sum, frequency> pairs before getting to the current node.
* We can imagine a path from the root to the current node. The sum from any node
* in the middle of the path to the current node = the difference between the sum
* from the root to the current node and the prefix sum of the node in the middle.
* 3. We are looking for some consecutive nodes that sum up to the given target value,
* which means the difference discussed in 2. should equal to the target value.
* In addition, we need to know how many differences are equal to the target value.
* 4. Here comes the map. The map stores the frequency of all possible sum in the path
* to the current node. If the difference between the current sum and the target
* value exists in the map, there must exist a node in the middle of the path,
* such that from this node to the current node, the sum is equal to the target value.
* 5. Note that there might be multiple nodes in the middle that satisfy what is
* discussed in 4. The frequency in the map is used to help with this.
* 6. Therefore, in each recursion, the map stores all information we need to calculate
& the number of ranges that sum up to target. Note that each range starts from a
* middle node, ended by the current node.
* 7. To get the total number of path count, we add up the number of valid paths ended
* by EACH node in the tree.
* 8. Each recursion returns the total count of valid paths in the subtree rooted at
* the current node. And this sum can be divided into three parts:
* - the total number of valid paths in the subtree rooted at the current node’s left child
* - the total number of valid paths in the subtree rooted at the current node’s right child
* - the number of valid paths ended by the current node
*/
class Solution
{
public:
int pathSum(TreeNode *root, int sum)
{
std::unordered_map<int, int> prefixSums;
prefixSums[0] = 1;
return pathSum(root, 0, sum, prefixSums);
}
private:
int pathSum(TreeNode *root, int curSum, int sum, std::unordered_map<int, int>& mp)
{
if (root == NULL)
return 0;
curSum += root->val;
int numNotEndedYet = mp.find(curSum - sum) != mp.end() ? mp[curSum-sum] : 0;
++mp[curSum];
numNotEndedYet += pathSum(root->left, curSum, sum, mp) + pathSum(root->right, curSum, sum, mp);
--mp[curSum];
return numNotEndedYet;
}
};
第 6 题：Binary Tree Maximum Path Sum
/**
* 6. Binary Tree Maximum Path Sum [124]
*
* Given a 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
* Given the below binary tree,
* 1
* / \
* 2 3
* Return 6.
* @endexample
* @example
* [9,6,-3,null,null,-6,2,null,null,2,null,-6,-6,-6]
* Return 16.
* @endexample
*/
class Solution
{
public:
int maxPathSum(TreeNode *root)
{
if (root == NULL)
return 0;
maxSum = -2147483648;
pathSum(root, maxSum);
return maxSum;
}
private:
int pathSum(TreeNode *root, int& maxSum)
{
int leftSum = root->left != NULL ? pathSum(root->left, maxSum) : 0;
int rightSum = root->right != NULL ? pathSum(root->right, maxSum) : 0;
int sum = root->val + leftSum + rightSum;
if (maxSum < sum)
maxSum = sum;
return root->val + std::max(leftSum >= rightSum ? leftSum : rightSum, 0);
}
};
注意返回的时候可以完全摒弃左右子树。
第 7 题：Diameter of Binary Tree
/**
* 7. Diameter of Binary Tree [543]
*
* 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].
* @endexample
* Note:
* The length of path between two nodes is represented by the number of edges between them.
*/
class Solution
{
public:
int diameterOfBinaryTree(TreeNode *root)
{
if (root == NULL)
return 0;
int diameter = 0;
diameterOfBinaryTree(root, diameter);
return diameter;
}
private:
int diameterOfBinaryTree(TreeNode *root, int& diameter)
{
int ldiameter = root->left != NULL ? diameterOfBinaryTree(root->left, diameter) : 0;
int rdiameter = root->right != NULL ? diameterOfBinaryTree(root->right, diameter) : 0;
if (diameter < ldiameter + rdiameter)
diameter = ldiameter + rdiameter;
return std::max(ldiameter, rdiameter) + 1;
}
};
第 8 题：Longest Univalue Path
/**
* 8. Longest Univalue Path [687]
*
* Given a binary tree, find the length of the longest path where each node
* in the path has the same value. This path may or may not pass through the root.
* @example
* Input:
* 5
* / \
* 4 5
* / \ \
* 1 1 5
* Output:
* 2
* @endexample
* @example
* Input:
* 1
* / \
* 4 5
* / \ \
* 4 4 5
* Output:
* 2
* @endexample
* Note:
* 1. The length of path between two nodes is represented by the number of
* edges between them.
* 2. The given binary tree has not more than 10000 nodes. The height of
* the tree is not more than 1000.
*/
class Solution
{
public:
int longestUnivaluePath(TreeNode *root)
{
if (root == NULL || root->left == NULL && root->right == NULL)
return 0;
int res = 0;
longestLength(root, res);
return res;
}
private:
int longestLength(TreeNode *root, int& longestL)
{
int leftL = 0, rightL = 0;
if (root->left != NULL)
{
leftL = longestLength(root->left, longestL) + 1;
if (root->left->val != root->val)
leftL = 0;
}
if (root->right != NULL)
{
rightL = longestLength(root->right, longestL) + 1;
if (root->right->val != root->val)
rightL = 0;
}
if (longestL < leftL + rightL)
longestL = leftL + rightL;
return std::max(leftL, rightL);
}
};
注意若孩子结点的值不同，需要将路径切断，否则加上与孩子结点之间的树边。
Miscellany
LeetCode 上有以下四道不容易分类的题目
第 1 题：Maximum Binary Tree
/**
* 1. Maximum Binary Tree [654]
*
* Given an integer array with no duplicates. A maximum tree
* building on this array is defined as follow:
* 1. The root is the maximum number in the array.
* 2. The left subtree is the maximum tree constructed from left part
* subarray divided by the maximum number.
* 3. The right subtree is the maximum tree constructed from right part
* subarray divided by the maximum number.
* Construct the maximum tree by the given array and output the root node of this tree.
* @example
* Input: [3,2,1,6,0,5]
* Output: return the tree root node representing the following tree:
* 6
* / \
* 3 5
* \ /
* 2 0
* \
* 1
* @endexample
* Note:
* The size of the given array will be in the range [1,1000].
*/
TreeNode* constructMaximumBinaryTree(std::vector<int>& nums)
{
if (nums.empty())
return NULL;
TreeNode sentinel(2147483647);
std::vector<TreeNode*> S(1, &sentinel);
for (size_t i = 0; i < nums.size(); ++i)
{
TreeNode *cur = new TreeNode(nums[i]);
while (S.back()->val < nums[i])
{
cur->left = S.back();
S.pop_back();
}
S.back()->right = cur;
S.push_back(cur);
}
return S[1];
}
第 2 题：Flatten Binary Tree to Linked List
/**
* 2. Flatten Binary Tree to Linked List [114]
*
* Given a binary tree, flatten it to a linked list in-place.
* @example
* Given
* 1
* / \
* 2 5
* / \ \
* 3 4 6
* The flattened tree should look like:
* 1
* \
* 2
* \
* 3
* \
* 4
* \
* 5
* \
* 6
* @endexample
* Hints:
* If you notice carefully in the flattened tree, each node's right child
* points to the next node of a pre-order traversal.
*/
void flatten(TreeNode *root)
{
while (root != NULL)
{
if (root->left != NULL && root->right != NULL)
{
TreeNode *t = root->left; // t is root->right 's predecessor
while (t->right != NULL)
t = t->right;
t->right = root->right;
}
if (root->left != NULL)
root->right = root->left;
root->left = NULL;
root = root->right;
}
}
第 3 题：Populating Next Right Pointers in Each Node
/**
* 3. Populating Next Right Pointers in Each Node [116]
*
* Given a binary tree
* struct TreeLinkNode {
* TreeLinkNode *left;
* TreeLinkNode *right;
* TreeLinkNode *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
* Given the following perfect binary tree,
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
* After calling your function, the tree should look like:
* 1 -> NULL
* / \
* 2 -> 3 -> NULL
* / \ / \
* 4->5->6->7 -> NULL
* @endexample
* Note:
* 1. You may only use constant extra space.
* 2. You may assume that it is a perfect binary tree (ie, all leaves are
* at the same level, and every parent has two children).
*/
void connect(TreeLinkNode *root)
{
if (root == NULL)
return;
TreeLinkNode *pre = root;
TreeLinkNode *cur = NULL;
while (pre->left != NULL)
{
cur = pre;
while (cur != NULL)
{
cur->left->next = cur->right;
if (cur->next != NULL)
cur->right->next = cur->next->left;
cur = cur->next;
}
pre = pre->left;
}
}
第 4 题：Populating Next Right Pointers in Each Node II
/**
* 4. Populating Next Right Pointers in Each Node II [117]
*
* What if the given tree could be any binary tree?
* Would your previous solution still work?
* @example
* Given the following binary tree,
* 1
* / \
* 2 3
* / \ \
* 4 5 7
* After calling your function, the tree should look like:
* 1 -> NULL
* / \
* 2 -> 3 -> NULL
* / \ \
* 4-> 5 -> 7 -> NULL
* @endexample
* Note:
* You may only use constant extra space.
*/
/**
* It's a BFS traversal. 'cur' pointer is the current level traveler and 'head' is the
* left most element at next level and the 'tail' is the right most element at next
* level till 'cur'. We move 'cur' pointer at current level and populate the the
* next-link at its children level. (Here the gist is we can move 'cur' to its next
* because this relationship was already populated in the previous round).
*/
void connect(TreeLinkNode *root)
{
TreeLinkNode *cur = root, *head = NULL, *tail = NULL;
while (cur != NULL)
{
if (cur->left != NULL)
{
if (tail != NULL)
tail = tail->next = cur->left;
else
head = tail = cur->left;
}
if (cur->right != NULL)
{
if (tail != NULL)
tail = tail->next = cur->right;
else
head = tail = cur->right;
}
if ((cur = cur->next) == NULL)
{
cur = head;
head = tail = NULL;
}
}
}
Binary Search Tree
二叉搜索树是最经典的一类二叉树，最大的特征就是中序遍历序列非递减，于是很多二叉搜索树的问题都可以通过中序遍历得以解决，其实现和两类二叉平衡树可详见 Binary Search Tree、AVL Tree、RB Tree。LeetCode 上有以下十四道与二叉搜索树相关的题目
第 1 题：Validate Binary Search Tree
/**
* 1. Validate Binary Search Tree [98]
*
* Given a binary tree, determine if it is a valid binary search tree (BST).
* @example
* 2
* / \
* 1 3
* Binary tree [2,1,3], return true.
* @endexample
* @example
* 1
* / \
* 2 3
* Binary tree [1,2,3], return false.
* @endexample
*/
bool isValidBST(TreeNode *root)
{
std::stack<TreeNode*> S;
TreeNode *p = root, *prev = NULL;
while (!S.empty() || p != NULL)
{
if (p != NULL)
{
S.push(p);
p = p->left;
}
else
{
p = S.top();
S.pop();
if (prev != NULL && prev->val >= p->val)
return false;
prev = p;
p = p->right;
}
}
return true;
}
第 2 题：Convert BST to Greater Tree
/**
* 2. Convert BST to Greater Tree [538]
*
* Given a Binary Search Tree (BST), convert it to a Greater Tree
* such that every key of the original BST is changed to the original
* key plus sum of all keys greater than the original key in BST.
* @example
* Input: The root of a Binary Search Tree like this:
* 5
* / \
* 2 13
* Output: The root of a Greater Tree like this:
* 18
* / \
* 20 13
* @endexample
*/
TreeNode* convertBST(TreeNode *root)
{
std::stack<TreeNode*> S;
TreeNode *p = root;
int sum = 0;
while (!S.empty() || p != NULL)
{
if (p != NULL)
{
S.push(p);
p = p->right;
}
else
{
p = S.top();
S.pop();
p->val += sum;
sum = p->val;
p = p->left;
}
}
return root;
}
第 3 题：Minimum Distance Between BST Nodes
/**
* 3. Minimum Distance Between BST Nodes [783]
*
* Given a Binary Search Tree (BST) with the root node root, return the
* minimum difference between the values of any two different nodes in the tree.
* @example
* Input: root = [4,2,6,1,3,null,null]
* Output: 1
* Explanation:
* Note that root is a TreeNode object, not an array.
* The given tree [4,2,6,1,3,null,null] is represented by the following diagram:
* 4
* / \
* 2 6
* / \
* 1 3
* while the minimum difference in this tree is 1, it occurs between
* node 1 and node 2, also between node 3 and node 2.
* @endexample
* Note:
* 1. The size of the BST will be between 2 and 100.
* 2. The BST is always valid, each node's value is an integer,
* and each node's value is different.
*/
int minDiffInBST(TreeNode *root)
{
int minDiff = 2147483647, predecessor = 0;
std::stack<TreeNode*> S;
TreeNode *p = root;
bool flag = false;
while (!S.empty() || p != NULL)
{
if (p != NULL)
{
S.push(p);
p = p->left;
}
else
{
p = S.top();
S.pop();
int diff = p->val >= predecessor ? p->val - predecessor : predecessor - p->val;
if (flag && minDiff > diff)
minDiff = diff;
if (!flag)
flag = true;
predecessor = p->val;
p = p->right;
}
}
return minDiff;
}
以上三题都是直接套用中序遍历的非递归实现模板即可。
第 4 题：Two Sum IV – Input is a BST
/**
* 4. Two Sum IV - Input is a BST [653]
*
* Given a Binary Search Tree and a target number, return true if there exist
* two elements in the BST such that their sum is equal to the given target.
* @example
* Input:
* 5
* / \
* 3 6
* / \ \
* 2 4 7
* Target = 9
* Output: True
* @endexample
* @example
* Input:
* 5
* / \
* 3 6
* / \ \
* 2 4 7
* Target = 28
* Output: False
* @endexample
*/
class Solution
{
public:
class iterator
{
public:
iterator(TreeNode *root, bool f) : p(root), forward(f)
{
++*this;
}
bool operator!()
{
return !S.empty() || p != NULL;
}
TreeNode* operator*()
{
return cur;
}
void operator++()
{
while (!S.empty() || p != NULL)
{
if (p != NULL)
{
S.push(p);
p = forward ? p->left : p->right;
}
else
{
p = S.top();
S.pop();
cur = p;
p = forward ? p->right : p->left;
break;
}
}
}
private:
bool forward;
TreeNode *cur;
TreeNode *p;
std::stack<TreeNode*> S;
};
bool findTarget(TreeNode *root, int k)
{
if (root == NULL || root->left == NULL && root->right == NULL)
return false;
iterator f(root, true), b(root, false);
while (*f != *b)
{
int sum = (*f)->val + (*b)->val;
if (sum < k)
++f;
else if (sum > k)
++b;
else
return true;
}
return false;
}
};
实现一个二叉搜索树的迭代器即可转换为 two pointers 问题从而得以解决。
第 5 题：Recover Binary Search Tree
/**
* 5. Recover Binary Search Tree [99]
*
* Two elements of a binary search tree (BST) are swapped by mistake.
* Recover the tree without changing its structure.
* Note:
* A solution using O(n) space is pretty straight forward.
* Could you devise a constant space solution?
*/
void recoverTree(TreeNode *root)
{
TreeNode *p = root, *prev = NULL, *t1 = NULL, *t2 = NULL;
while (p != NULL)
{
if (p->left != NULL)
{
TreeNode *predecessor = p->left;
while (predecessor->right != NULL && predecessor->right != p)
predecessor = predecessor->right;
if (predecessor->right == NULL)
{
predecessor->right = p;
p = p->left;
}
else
{
predecessor->right = NULL;
if (t1 == NULL && prev != NULL && p->val < prev->val)
t1 = prev;
if (t1 != NULL && p->val < prev->val)
t2 = p;
prev = p;
p = p->right;
}
}
else
{
if (t1 == NULL && prev != NULL && p->val < prev->val)
t1 = prev;
if (t1 != NULL && p->val < prev->val)
t2 = p;
prev = p;
p = p->right;
}
}
std::swap(t1->val, t2->val);
}
要求 O(1) 的空间复杂度就用 Morris 遍历方式。
第 6 题：Convert Sorted Array to Binary Search Tree
/**
* 6. Convert Sorted Array to Binary Search Tree [108]
*
* Given an array where elements are sorted in ascending order,
* convert it to a height balanced BST.
* For this problem, a height-balanced binary tree is defined as
* a binary tree in which the depth of the two subtrees of
* every node never differ by more than 1.
* @example
* Given the sorted array: [-10,-3,0,5,9],
* One possible answer is: [0,-3,9,-10,null,5],
* which represents the following height balanced BST:
* 0
* / \
* -3 9
* / /
* -10 5
* @endexample
*/
class Solution
{
public:
TreeNode* sortedArrayToBST(std::vector<int>& nums)
{
if (nums.empty())
return NULL;
return constructSubtree(nums, 0, nums.size() - 1);
}
private:
TreeNode* constructSubtree(std::vector<int>& nums, int begin, int end)
{
int mid = begin + end + 1 >> 1;
TreeNode *root = new TreeNode(nums[mid]);
if (begin < mid)
root->left = constructSubtree(nums, begin, mid-1);
if (mid < end)
root->right = constructSubtree(nums, mid+1, end);
return root;
}
};
要求得到平衡二叉树，不断对半分割即可。
第 7 题：Convert Sorted List to Binary Search Tree
/**
* 7. Convert Sorted List to Binary Search Tree [109]
*
* Given a singly linked list where elements are sorted in ascending order,
* convert it to a height balanced BST.
* For this problem, a height-balanced binary tree is defined as
* a binary tree in which the depth of the two subtrees of
* every node never differ by more than 1.
* @example
* Given the sorted array: [-10,-3,0,5,9],
* One possible answer is: [0,-3,9,-10,null,5],
* which represents the following height balanced BST:
* 0
* / \
* -3 9
* / /
* -10 5
* @endexample
*/
class Solution
{
public:
TreeNode* sortedListToBST(ListNode *head)
{
if (head == NULL)
return NULL;
return constructSubtree(head, NULL);
}
private:
TreeNode* constructSubtree(ListNode *begin, ListNode *end)
{
ListNode *p = begin, *q = p;
while (q->next != end)
{
p = p->next;
q = q->next;
if (q->next == end)
break;
q = q->next;
}
TreeNode *root = new TreeNode(p->val);
if (begin->val < p->val)
root->left = constructSubtree(begin, p);
if (p->val < q->val)
root->right = constructSubtree(p->next, q->next);
return root;
}
};
输入变成了单链表怎么办？采用快慢指针进行对半分割。
第 8 题：Delete Node in a BST
/**
* 8. Delete Node in a BST [450]
*
* 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.
* @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
* Another valid answer is [5,2,6,null,4,null,7].
* 5
* / \
* 2 6
* \ \
* 4 7
* @endexample
* Note:
* Time complexity should be O(height of tree).
*/
TreeNode* deleteNode(TreeNode *root, int key)
{
if (root == NULL)
return NULL;
if (key < root->val)
root->left = deleteNode(root->left, key);
else if (key > root->val)
root->right = deleteNode(root->right, key);
else
{
TreeNode *child = root->left != NULL ? root->left : root->right;
if (root->left != NULL)
{
TreeNode *predecessor = root->left;
while (predecessor->right != NULL)
predecessor = predecessor->right;
predecessor->right = root->right;
}
delete root;
root = child;
}
return root;
}
很经典的操作，采用前驱或是后继的方式都可以，该实现中采用了前驱。
第 9 题：Kth Smallest Element in a BST
/**
* 9. Kth Smallest Element in a BST [230]
*
* Given a binary search tree, write a function kthSmallest to find
* the kth smallest element in it.
* Note:
* You may assume k is always valid, 1 <= k <= BST's total elements.
* Follow up:
* What if the BST is modified (insert/delete operations) often and you need to
* find the kth smallest frequently? How would you optimize the kthSmallest routine?
*/
class Solution
{
public:
int kthSmallest(TreeNode *root, int k)
{
int count = leftNodes(root->left);
if (k <= count)
return kthSmallest(root->left, k);
else if (k == count + 1)
return root->val;
else
return kthSmallest(root->right, k - count - 1);
}
private:
int leftNodes(TreeNode *root)
{
return root != NULL ? 1 + leftNodes(root->left) + leftNodes(root->right) : 0;
}
};
根据左子树的结点个数和当前的 k 决定继续往哪侧子树递归，注意往右侧子树递归的时候 k 需要调整。
第 10 题：Trim a Binary Search Tree
/**
* 10. Trim a Binary Search Tree [669]
*
* Given a binary search tree and the lowest and highest boundaries
* as L and R, trim the tree so that all its elements lies in [L, R]
* (R >= L). You might need to change the root of the tree, so the
* result should return the new root of the trimmed binary search tree.
* @example
* Input:
* 1
* / \
* 0 2
* L = 1
* R = 2
* Output:
* 1
* \
* 2
* @endexample
* @example
* Input:
* 3
* / \
* 0 4
* \
* 2
* /
* 1
* L = 1
* R = 3
* Output:
* 3
* /
* 2
* /
* 1
* @endexample
* @example
* Input: [3,0,7,null,2,6,9,1,null,4,null,8,null,null,null,null,5]
* L = 2
* R = 5
* Output: [3,2,4,null,null,null,5]
* @endexample
*/
TreeNode* trimBST(TreeNode *root, int L, int R)
{
if (root == NULL)
return NULL;
if (root->val < L)
return trimBST(root->right, L, R);
if (root->val > R)
return trimBST(root->left, L, R);
root->left = trimBST(root->left, L, R);
root->right = trimBST(root->right, L, R);
return root;
}
该实现中为了简洁起见，并未释放内存，在实践当中需要慎重考虑内存泄漏问题。
第 11 题：Split BST
/**
* 11. Split BST [776]
*
* Given a Binary Search Tree (BST) with root node root, and a target value V,
* split the tree into two subtrees where one subtree has nodes that are all
* smaller or equal to the target value, while the other subtree has all nodes
* that are greater than the target value. It's not necessarily the case that
* the tree contains a node with value V.
* Additionally, most of the structure of the original tree should remain.
* Formally, for any child C with parent P in the original tree, if they are both
* in the same subtree after the split, then node C should still have the parent P.
* You should output the root TreeNode of both subtrees after splitting, in any order.
* @example
* Input: root = [4,2,6,1,3,5,7], V = 2
* Output: [[2,1],[4,3,6,null,null,5,7]]
* Explanation:
* Note that root, output[0], and output[1] are TreeNode objects, not arrays.
* The given tree [4,2,6,1,3,5,7] is represented by the following diagram:
* 4
* / \
* 2 6
* / \ / \
* 1 3 5 7
* while the diagrams for the outputs are:
* 4
* / \
* 3 6 and 2
* / \ /
* 5 7 1
* @endexample
* Note:
* 1. The size of the BST will not exceed 50.
* 2. The BST is always valid and each node's value is different.
*/
std::vector<TreeNode*> splitBST(TreeNode *root, int V)
{
if (root == NULL)
return std::vector<TreeNode*>(2, NULL);
if (root->val <= V)
{
std::vector<TreeNode*> res = splitBST(root->right, V);
root->right = res[0];
res[0] = root;
return res;
}
else
{
std::vector<TreeNode*> res = splitBST(root->left, V);
root->left = res[1];
res[1] = root;
return res;
}
}
第 12 题：Lowest Common Ancestor of a Binary Search Tree
/**
* 12. Lowest Common Ancestor of a Binary Search Tree [235]
*
* Given a binary search tree (BST), find the lowest common ancestor (LCA)
* of two given nodes in the BST.
* According to the definition of LCA on Wikipedia: "The lowest common ancestor
* is defined between two nodes v and w as the lowest node in T that has both
* v and w as descendants (where we allow a node to be a descendant of itself)."
* @example
* _______6______
* / \
* ___2__ ___8__
* / \ / \
* 0 _4 7 9
* / \
* 3 5
* The lowest common ancestor (LCA) of nodes 2 and 8 is 6.
* Another example is LCA of nodes 2 and 4 is 2, since a node can be
* a descendant of itself according to the LCA definition.
* @endexample
*/
TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
{
while ((root->val > p->val && root->val > q->val) || (root->val < p->val && root->val < q->val))
root = p->val < root->val ? root->left : root->right;
return root;
}
最近共同祖先问题，在二叉搜索树的条件下可以根据结点的值比较来判断。
第 13 题：Lowest Common Ancestor of a Binary Tree
/**
* 13. Lowest Common Ancestor of a Binary Tree [236]
*
* 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 v and w as the lowest node in T that has both
* v and w as descendants (where we allow a node to be a descendant of itself)."
* @example
* _______3______
* / \
* ___5__ ___1__
* / \ / \
* 6 _2 0 8
* / \
* 7 4
* The lowest common ancestor (LCA) of nodes 5 and 1 is 3.
* Another example is LCA of nodes 5 and 4 is 5, since a node can be
* a descendant of itself according to the LCA definition.
* @endexample
*/
/**
* If the current (sub)tree contains both p and q, then the function result is their LCA.
* If only one of them is in that subtree, then the result is that one of them.
* If neither are in that subtree, the result is NULL.
*/
TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
{
if (root == NULL || root == p || root == q)
return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
return left == NULL ? right : right == NULL ? left : root;
}
若是普通的二叉树，就不能根据结点的值来解决问题了。
第 14 题：Find Mode in Binary Search Tree
/**
* 14. Find Mode in Binary Search Tree [501]
*
* Given a binary search tree (BST) with duplicates, find all the
* mode(s) (the most frequently occurred element) in the given BST.
* Assume a BST is defined as follows:
* 1. The left subtree of a node contains only nodes with keys less than
* or equal to the node's key.
* 2. The right subtree of a node contains only nodes with keys greater
* than or equal to the node's key.
* 3. Both the left and right subtrees must also be binary search trees.
* @example
* Given BST [1,null,2,2],
* 1
* \
* 2
* /
* 2
* return [2].
* @endexample
* Note:
* If a tree has more than one mode, you can return them in any order.
* Follow up:
* Could you do that without using any extra space? (Assume that the implicit
* stack space incurred due to recursion does not count).
*/
class Solution
{
public:
std::vector<int> findMode(TreeNode *root)
{
std::vector<int> res;
int preVal = 0, count = 1, maxCount = 0;
inorder(root, preVal, count, maxCount, res);
return res;
}
private:
void inorder(TreeNode *root, int& preVal, int& count, int& maxCount, std::vector<int>& modes)
{
if (root != NULL)
{
inorder(root->left, preVal, count, maxCount, modes);
if (!modes.empty())
{
if (root->val != preVal)
count = 1;
else
++count;
}
if (maxCount <= count)
{
if (maxCount < count)
modes.clear();
modes.push_back(root->val);
maxCount = count;
}
preVal = root->val;
inorder(root->right, preVal, count, maxCount, modes);
}
}
};
频数相关的题，不过该题并未采用哈希表（题目中要求 O(1) 空间复杂度），而是每次发现频数更高的元素的时候，就清除容器内现有的元素，若频数相同，则存入容器。
Disjoint Set Union
并查集在采用了按秩合并和路径压缩后可以在非常接近线性的时间内判定两个元素是否处于同个集合，其实现如下：
class DSU
{
public:
DSU(int _n) : rank(_n, 0), parent(_n, 0)
{
for (int i = 1; i < _n; ++i)
parent[i] = i;
}
int find(int x)
{
if (x != parent[x])
parent[x] = find(parent[x]);
return parent[x];
}
bool link(int x, int y)
{
int px = find(x), py = find(y);
if (px == py)
return false;
if (rank[px] > rank1)
parent1 = px;
else
{
parent[px] = py;
if (rank[px] == rank1)
++rank1;
}
return true;
}
private:
std::vector<int> rank;
std::vector<int> parent;
};
LeetCode 上有以下两道与并查集相关的题目
第 1 题：Redundant Connection
/**
* 1. Redundant Connection [684]
*
* In this problem, a tree is an undirected graph that is connected and has no cycles.
* The given input is a graph that started as a tree with N nodes (with distinct
* values 1, 2, ..., N), with one additional edge added. The added edge has two
* different vertices chosen from 1 to N, and was not an edge that already existed.
* The resulting graph is given as a 2D-array of edges. Each element of edges is a
* pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.
* Return an edge that can be removed so that the resulting graph is a tree of N nodes.
* If there are multiple answers, return the answer that occurs last in the given
* 2D-array. The answer edge [u, v] should be in the same format, with u < v.
* @example
* Input: [[1,2], [1,3], [2,3]]
* Output: [2,3]
* Explanation: The given undirected graph will be like this:
* 1
* / \
* 2 - 3
* @endexample
* @example
* Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
* Output: [1,4]
* Explanation: The given undirected graph will be like this:
* 5 - 1 - 2
* | |
* 4 - 3
* @endexample
* Note:
* 1. The size of the input 2D-array will be between 3 and 1000.
* 2. Every integer represented in the 2D-array will be between 1 and N,
* where N is the size of the input array.
*/
class Solution
{
public:
std::vector<int> findRedundantConnection(std::vector<std::vector<int> >& edges)
{
std::vector<int> res(2, 0);
std::vector<int> parent(1001, 0);
for (int i = 0; i < 1001; ++i)
parent[i] = i;
for (size_t k = 0; k < edges.size(); ++k)
{
int u = edges[k][0], v = edges[k][1];
int pu = find(parent, u), pv = find(parent, v);
if (pu != pv)
parent[pv] = pu;
else
{
res[0] = u, res[1] = v;
break;
}
}
return res;
}
private:
int find(std::vector<int>& parent, int x)
{
if (x != parent[x])
parent[x] = find(parent, parent[x]);
return parent[x];
}
};
每次都将已经访问的结点合并为一个集合，如果新结点单独成集合，则表明该结点需要树边来连接，如果新结点已经在旧的集合中了，表明此结点上必然存在一条多余的边。该题若采用并查集现成类 DSU，则实现极为简洁
std::vector<int> findRedundantConnection(std::vector<std::vector<int> >& edges)
{
std::vector<int> res(2, 0);
DSU dsu(1001);
for (size_t k = 0; k < edges.size(); ++k)
{
int u = edges[k][0], v = edges[k][1];
if (!dsu.link(u, v))
{
res[0] = u, res[1] = v;
break;
}
}
return res;
}
第 2 题：Redundant Connection II
/**
* 2. Redundant Connection II [685]
*
* In this problem, a rooted tree is a directed graph such that, there is exactly
* one node (the root) for which all other nodes are descendants of this node, plus
* every node has exactly one parent, except for the root node which has no parents.
* The given input is a graph that started as a rooted tree with N nodes (with distinct
* values 1, 2, ..., N), with one additional edge added. The added edge has two
* different vertices chosen from 1 to N, and was not an edge that already existed.
* The resulting graph is given as a 2D-array of edges. Each element of edges is a
* pair [u, v] with u < v, that represents a directed edge connecting nodes u and v,
* where u is a parent of child v.
* Return an edge that can be removed so that the resulting graph is a rooted tree
* of N nodes. If there are multiple answers, return the answer that occurs last
* in the given 2D-array.
* @example
* Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
* Output: [4,1]
* Explanation: The given directed graph will be like this:
* 5 <- 1 -> 2
* ^ |
* | v
* 4 <- 3
* @endexample
* @example
* Input: [[4,2],[1,5],[5,2],[5,3],[2,4]]
* Output: [4,2]
* Explanation: The given directed graph will be like this:
* 1 --> 5 --> 3
* |
* v
* 2 <-> 4
* @endexample
* @example
* Input: [[2,1],[3,1],[4,2],[1,4]]
* Output: [2,1]
* Explanation: The given directed graph will be like this:
* 3 --> 1 --> 4
* ^ |
* | |
* 2 <--
* @endexample
* Note:
* 1. The size of the input 2D-array will be between 3 and 1000.
* 2. Every integer represented in the 2D-array will be between 1 and N,
* where N is the size of the input array.
*/
/**
* By adding one edge (parent->child) to the tree:
* 1. every node including root has exactly one parent, if child is root;
* 2. root does not have parent, one node (child) has 2 parents, and all
* other nodes have exactly 1 parent, if child is not root.
* After adding the extra edge, the graph can be generalized in 3 different cases:
* root ...> a --> c ...> d | root ...> a --> c ...> d | a --> root ...> d
* . e1 ^ | e1 ^ . | ^ e1 .
* . e2 | | | e2 v | e2 | v
* ......> b ----+ | +----- b | x --> b <... c ...> f
* Case 1: "c" is the only node which has 2 parents and there is not path
* (c->...->b) which means no cycle. In this case, removing either "e1" or "e2"
* will make the tree valid. According to the description of the problem,
* whichever edge added later is the answer.
* Case 2: "c" is the only node which has 2 parents and there is a path(c->...->b)
* which means there is a cycle. In this case, "e2" is the only edge that should
* be removed. Removing "e1" will make the tree in 2 separated groups. Note,
* in input edges, "e1" may come after "e2".
* Case 3: this is how it looks like if edge (a->root) is added to the tree.
* Removing any of the edges along the cycle will make the tree valid. But
* according to the description of the problem, the last edge added to complete
* the cycle is the answer. Note: edge "e2" (an edge pointing from a node outside
* of the cycle to a node on the cycle) can never happen in this case.
* As we can see from the pictures, the answer must be:
* 1. one of the 2 edges that pointing to the same node in case 1 and case 2;
* there is one and only one such node which has 2 parents.
* 2. the last edge added to complete the cycle in case 3.
* Note: both case 2 and case 3 have cycle, but in case 2, "e2" may not be the
* last edge added to complete the cycle.
*
* Now, we can apply Disjoint Set (DS) to build the tree in the order the edges
* are given. We define ds[i] as the parent or ancestor of node i. It will become
* the root of the whole tree eventually if edges does not have extra edge.
* When given an edge (a->b), we find node a's ancestor and assign it to ds[b].
* Note, in typical DS, we also need to find node b's ancestor and assign a's
* ancestor as the ancestor of b's ancestor. But in this case, we don't have to,
* since we skip the second parent edge (see below), it is guaranteed a is the
* only parent of b.
* If we find an edge pointing to a node that already has a parent, we simply
* skip it. The edge skipped can be "e1" or "e2" in case 1 and case 2. In case 1,
* removing either "e1" or "e2" will make the tree valid. In case 3, removing "e2"
* will make the tree valid, but removing "e1" will make the tree in 2 separated
* groups and one of the groups has a cycle. In case 3, none of the edges will be
* skipped because there is no 2 edges pointing to the same node. The result is a
* graph with cycle and n edges.
*
* How to detect cycle by using Disjoint Set (Union Find)?
* When we join 2 nodes by edge (a->b), we check a's ancestor, if it is b, we find
* a cycle! When we find a cycle, we don't assign a's ancestor as b's ancestor.
* That will trap our code in endless loop. We need to save the edge though since
* it might be the answer in case 3.
* Now the code. We define two variables (first and second) to store the 2 edges
* that point to the same node if there is any (there may not be such edges, see case 3).
* We skip adding second to tree. first and second hold the values of the original
* index in input edges of the 2 edges respectively. Variable last is the edge added
* to complete a cycle if there is any (there may not be a cycle, see case 1 and
* removing "e2" in case 2). And it too hold the original index in input edges.
* After adding all except at most one edges to the tree, we end up with 4 different scenario:
* 1. case 1 with either "e1" or "e2" removed. Either way, the result tree is valid.
* The answer is the edge being removed or skipped (a.k.a. second)
* 2. case 2 with "e2" removed. The result tree is valid. The answer is the edge
* being removed or skipped (a.k.a. second)
* 3. case 2 with "e2" removed. The result tree is invalid with a cycle in one of the groups.
* The answer is the other edge (first) that points to the same node as second.
* 4. case 3 with no edge removed. The result tree is invalid with a cycle.
* The answer is the last edge added to complete the cycle.
* In the following code,
* last == -1 means "no cycle found" which is scenario 1 or 2;
* second != -1 && last != -1 means "one edge removed and the result tree has cycle"
* which is scenario 3;
* second == -1 means "no edge skipped or removed" which is scenario 4.
*/
class Solution
{
public:
std::vector<int> findRedundantDirectedConnection(std::vector<std::vector<int> >& edges)
{
int n = static_cast<int>(edges.size());
std::vector<int> parent(n+1, -1);
std::vector<int> ds(n+1, 0);
int first = -1, second = -1, last = -1;
for (int i = 0; i < n; ++i)
{
int u = edges[i][0], v = edges[i][1];
if (parent[v] == -1)
{
parent[v] = i;
int pu = find(ds, u);
if (pu != v)
ds[v] = pu;
else // find circle
last = i;
}
else // dup parents
{
first = parent[v];
second = i;
}
}
if (last == -1) // no cycle found by removing second
return edges[second];
if (second == -1) // no edge removed
return edges[last];
return edges[first];
}
private:
int find(std::vector<int>& parent, int x)
{
if (parent[x] != 0) // 0 is the dummy root, i.e., parent[root] = 0
return parent[x] = find(parent, parent[x]);
return x; // here x is the root
}
};
Serialization
序列化即是将二叉树转换为字符串的形式得以在硬盘上保存或是在网络上传输，根据序列化所得的字符串可以重建二叉树。LeetCode 上有以下五道与序列化二叉树相关的题目
第 1 题：Verify Preorder Serialization of a Binary Tree
/**
* 1. Verify Preorder Serialization of a Binary Tree [331]
*
* One way to serialize a binary tree is to use pre-order traversal.
* When we encounter a non-null node, we record the node's value.
* If it is a null node, we record using a sentinel value such as #.
* _9_
* / \
* 3 2
* / \ / \
* 4 1 # 6
* / \ / \ / \
* # # # # # #
* For example, the above binary tree can be serialized to the string
* "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.
* Given a string of comma separated values, verify whether it is a correct
* preorder traversal serialization of a binary tree. Find an algorithm
* without reconstructing the tree. Each comma separated value in the string
* must be either an integer or a character '#' representing null pointer.
* You may assume that the input format is always valid, for example it
* could never contain two consecutive commas such as "1,,3".
* @example
* "9,3,4,#,#,1,#,#,2,#,6,#,#"
* Return true
* @endexample
* @example
* "1,#"
* Return false
* @endexample
* @example
* "9,#,#,1"
* Return false
* @endexample
*/
bool isValidSerialization(std::string preorder)
{
if (preorder.empty())
return false;
if (preorder[0] == '#')
return preorder.size() == 1;
if (preorder.size() == 1)
return preorder[0] == '#';
std::vector<int> remainingChild;
remainingChild.reserve(64);
for (size_t i = 1; i < preorder.size(); ++i)
{
if (preorder[i] == ',' && preorder[i-1] != '#')
remainingChild.push_back(2);
else if (preorder[i] == '#')
{
while (!remainingChild.empty() && --remainingChild.back() == 0)
remainingChild.pop_back();
if (remainingChild.empty() && i < preorder.size()-1)
return false;
}
}
return remainingChild.empty();
}
第 2 题：Find Duplicate Subtrees
/**
* 2. Find Duplicate Subtrees [652]
*
* Given a binary tree, return all duplicate subtrees. For each kind of
* duplicate subtrees, you only need to return the root node of any one of them.
* Two trees are duplicate if they have the same structure with same node values.
* @example
* 1
* / \
* 2 3
* / / \
* 4 2 4
* /
* 4
* The following are two duplicate subtrees:
* 2
* /
* 4
* and
* 4
* Therefore, you need to return above trees' root in the form of a list.
* @endexample
*/
class Solution
{
public:
std::vector<TreeNode*> findDuplicateSubtrees(TreeNode *root)
{
std::vector<TreeNode*> res;
std::map<std::string, int> dupTimes;
serialize(root, dupTimes, res);
return res;
}
private:
std::string serialize(TreeNode *root, std::map<std::string, int>& mp, std::vector<TreeNode*>& res)
{
if (root == NULL)
return "#";
std::string serial = serialize(root->left, mp, res);
serial.push_back(',');
serial.append(serialize(root->right, mp, res));
serial.push_back(',');
serial.append(std::to_string(root->val));
if (++mp[serial] == 2)
res.push_back(root);
return serial;
}
};
序列化 + 字符串哈希 + 后序遍历构成了该题的解法，一道比较巧妙特殊题目。
第 3 题：Construct String from Binary Tree
/**
* 3. Construct String from Binary Tree [606]
*
* You need to construct a string consists of parenthesis and
* integers from a binary tree with the preorder traversing way.
* The null node needs to be represented by empty parenthesis
* pair "()". And you need to omit all the empty parenthesis pairs
* that don't affect the one-to-one mapping relationship between
* the string and the original binary tree.
* @example
* Input: Binary tree: [1,2,3,4]
* 1
* / \
* 2 3
* /
* 4
* Output: "1(2(4))(3)"
* Explanation: Originallay it needs to be "1(2(4)())(3()())",
* but you need to omit all the unnecessary empty parenthesis pairs.
* And it will be "1(2(4))(3)".
* @endexample
* @example
* Input: Binary tree: [1,2,3,null,4]
* 1
* / \
* 2 3
* \
* 4
* Output: "1(2()(4))(3)"
* Explanation: Almost the same as the first example,
* except we can't omit the first parenthesis pair to break the
* one-to-one mapping relationship between the input and the output
* @endexample
*/
class Solution
{
public:
std::string tree2str(TreeNode *t)
{
if (t == NULL)
return "";
std::string res;
preorder(t, res);
return res;
}
private:
void preorder(TreeNode *root, std::string& data)
{
data.append(std::to_string(root->val));
if (root->left != NULL)
{
data.push_back('(');
preorder(root->left, data);
data.push_back(')');
}
if (root->right != NULL)
{
if (root->left == NULL)
data.append("()");
data.push_back('(');
preorder(root->right, data);
data.push_back(')');
}
}
};
第 4 题：Serialize and Deserialize BST
/**
* 4. Serialize and Deserialize BST [449]
*
* Serialization is the process of converting a data structure or object
* into a sequence of bits so that it can be stored in a file or memory
* buffer, or transmitted across a network connection link to be
* reconstructed later in the same or another computer environment.
* Design an algorithm to serialize and deserialize a binary search tree.
* There is no restriction on how your serialization/deserialization
* algorithm should work. You just need to ensure that a binary search
* tree can be serialized to a string and this string can be deserialized
* to the original tree structure.
* The encoded string should be as compact as possible.
* Note:
* Do not use class member/global/static variables to store states.
* Your serialize and deserialize algorithms should be stateless.
*/
class Codec
{
public:
// Encodes a tree to a single string.
std::string serialize(TreeNode *root)
{
std::string data;
preorder(root, data);
return data;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(std::string data)
{
size_t pos = 0;
return reconstruct(data, pos, -2147483648, 2147483647);
}
private:
void preorder(TreeNode *root, std::string& data)
{
if (root != NULL)
{
char buf[4];
memcpy(buf, &root->val, sizeof(int));
for (int i = 0; i < 4; ++i)
data.push_back(buf[i]);
preorder(root->left, data);
preorder(root->right, data);
}
}
TreeNode* reconstruct(std::string& buf, size_t& pos, int minVal, int maxVal)
{
if (pos >= buf.size())
return NULL;
int value = 0;
memcpy(&value, &buf[pos], sizeof(int));
if (value < minVal || value > maxVal)
return NULL;
TreeNode *node = new TreeNode(value);
pos += sizeof(int);
node->left = reconstruct(buf, pos, minVal, value);
node->right = reconstruct(buf, pos, value, maxVal);
return node;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
以二进制格式保存最小化了空间需求，除了采用 memcpy() 来进行类型转换，也可采用 reinterpret_cast<> 强制类型转换符来进行类型转换。
第 5 题：Serialize and Deserialize Binary Tree
/**
* 5. Serialize and Deserialize Binary Tree [297]
*
* Serialization is the process of converting a data structure or object into
* a sequence of bits so that it can be stored in a file or memory buffer,
* or transmitted across a network connection link to be reconstructed later
* in the same or another computer environment.
* Design an algorithm to serialize and deserialize a binary tree. There is
* no restriction on how your serialization/deserialization algorithm should
* work. 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.
* @example
* You may serialize the following tree
* 1
* / \
* 2 3
* / \
* 4 5
* as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ
* serializes a binary tree.
* @endexample
* @example
* You may serialize the following tree
* ___1___
* / \
* __6__ 2
* / \
* _7_ _5_
* / / \
* 8 6 4
* / \ / \
* 7 9 3 5
* / \ / \
* 10 8 4 2
* /\ /
* 9 11 2
* as "[1,6,2,7,5,null,null,8,null,6,4,7,9,null,null,3,5,
* null,null,10,8,4,2,null,null,9,11,null,null,2]"
* @endexample
* Note:
* Do not use class member/global/static variables to store states.
* Your serialize and deserialize algorithms should be stateless.
*/
class Codec
{
public:
// Encodes a tree to a single string.
std::string serialize(TreeNode *root)
{
std::string data;
if (root == NULL)
return data;
std::deque<TreeNode*> Q;
Q.push_back(root);
data.append(std::to_string(root->val));
data.push_back(',');
bool notLowest2Level = false;
int visited = 0, total = 1, nextTotal = 0;
while (!Q.empty())
{
TreeNode *p = Q[visited];
if (p->left != NULL)
{
Q.push_back(p->left);
if (!notLowest2Level)
notLowest2Level = p->left->left != NULL || p->left->right != NULL;
++nextTotal;
}
if (p->right != NULL)
{
Q.push_back(p->right);
if (!notLowest2Level)
notLowest2Level = p->right->left != NULL || p->right->right != NULL;
++nextTotal;
}
if (++visited == total)
{
bool appendNull = nextTotal > 0;
for (int i = 0, k = 0; i < total-1; ++i)
{
TreeNode *q = Q.front();
if (q->left != NULL)
{
data.append(std::to_string(q->left->val));
data.push_back(','); ++k;
}
else if (appendNull && (k < nextTotal || notLowest2Level))
data.append("null,");
if (q->right != NULL)
{
data.append(std::to_string(q->right->val));
data.push_back(','); ++k;
}
else if (appendNull && (k < nextTotal || notLowest2Level))
data.append("null,");
Q.pop_front();
}
if (p->left != NULL)
{
data.append(std::to_string(p->left->val));
data.push_back(',');
if (p->right != NULL)
{
data.append(std::to_string(p->right->val));
data.push_back(',');
}
else if (nextTotal > 0)
data.append("null,");
}
else
{
if (p->right != NULL)
{
data.append("null,");
data.append(std::to_string(p->right->val));
data.push_back(',');
}
else if (nextTotal > 0)
data.append("null,null,");
}
Q.pop_front();
notLowest2Level = false;
visited = 0;
total = nextTotal;
nextTotal = 0;
}
}
while (data.back() < '0' || data.back() > '9')
data.pop_back();
return data;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(std::string data)
{
TreeNode dummyRoot(0), *pDummy = &dummyRoot;
std::queue<std::pair<TreeNode**, int> > Q;
Q.push(std::pair<TreeNode**, int>(&pDummy, 1));
bool isDigit = false;
int comma = -1;
data.push_back(',');
int n = static_cast<int>(data.size());
for (int i = 0; i < n; ++i)
{
if (data[i] == ',')
{
if (isDigit)
{
std::string vals = data.substr(comma+1, i-comma-1);
int val = atoi(vals.c_str());
TreeNode **p = Q.front().first;
int slot = Q.front().second;
if (slot == 2)
{
(*p)->left = new TreeNode(val);
--Q.front().second;
Q.push(std::pair<TreeNode**, int>(&(*p)->left, 2));
}
else if (slot == 1)
{
(*p)->right = new TreeNode(val);
Q.pop();
Q.push(std::pair<TreeNode**, int>(&(*p)->right, 2));
}
}
else if (--Q.front().second == 0)
Q.pop();
comma = i;
}
else
isDigit = data[i] >= '0' && data[i] <= '9';
}
return dummyRoot.right;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
本题即是实现 LeetCode 平台所采用的二叉树序列化、反序列化算法。