Algorithms: Tree
树相关题目：
- 先序
- 中序
- 后序
- DFS其他遍历方式（如右左根）
- 层序遍历
if (!root) xxx; //应对只有左子树或只有右子树的情况
if (!root->left && !root->right) xxx;//应对叶子节点的情况
144. Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
- 返回先序遍历的结果。其中使用迭代时要用栈保存应该的遍历顺序。访问栈顶元素，栈顶的right节点先压入栈中，栈顶的left节点再压入栈中。
// 递归
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorder(root, res);
return res;
}
void preorder(TreeNode *root, vector<int> &res) {
if (!root) return;
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
// 迭代
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
stack<TreeNode*> nodeStack;
nodeStack.push(root);
while (!nodeStack.empty()) {
TreeNode* tmp = nodeStack.top();
nodeStack.pop();
res.push_back(tmp->val);
if (tmp->right) nodeStack.push(tmp->right);
if (tmp->left) nodeStack.push(tmp->left);
}
return res;
}
94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].
- 返回中序遍历的结果。其中使用迭代时要用栈保存应该的遍历顺序。如果没访问过栈顶的左节点，将左节点压入栈中；其他情况时，栈顶元素加入结果，并把栈顶元素的右节点压入栈中。
// 递归
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
void inorder(TreeNode *root, vector<int> &res) {
if(!root) return;
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
// 迭代
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
stack<TreeNode*> nodeStack;
unordered_map<TreeNode*, bool> visited;
nodeStack.push(root);
while (!nodeStack.empty()) {
TreeNode* tmp = nodeStack.top();
if (tmp->left && !visited[tmp]) {
nodeStack.push(tmp->left);
visited[tmp] = true;
} else {
res.push_back(tmp->val);
nodeStack.pop();
if (tmp->right) nodeStack.push(tmp->right);
}
}
return res;
}
145. Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
- 返回后序遍历的结果。
// 递归
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
postorder(root, res);
return res;
}
void postorder(TreeNode* root, vector<int> &res) {
if (!root) return;
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val);
}
// 迭代1，使用类似先序遍历的方式，使用中-右-左的的入栈顺序，加入结果的顺序为逆序，即左-右-中的顺序
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
if (!root) return res;
stack<TreeNode*> nodeStack;
nodeStack.push(root);
while (!nodeStack.empty()) {
TreeNode *tmp = nodeStack.top();
nodeStack.pop();
res.insert(res.begin(), tmp->val);
if (tmp->left) nodeStack.push(tmp->left);
if (tmp->right) nodeStack.push(tmp->right);
}
return res;
}
// 迭代2，使用类似中序遍历的方式，记录每个点是否被访问过
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
if (!root) return res;
stack<TreeNode*> nodeStack;
unordered_map<TreeNode*, bool> visited;
nodeStack.push(root);
while (!nodeStack.empty()) {
TreeNode *tmp = nodeStack.top();
if (tmp->left && !visited[tmp->left]) {
nodeStack.push(tmp->left);
visited[tmp->left] = true;
} else if (tmp->right && !visited[tmp->right]) {
nodeStack.push(tmp->right);
visited[tmp->right] = true;
} else {
nodeStack.pop();
res.push_back(tmp->val);
}
}
return res;
}
98. Validate Binary Search Tree
- 验证二叉搜索树是否合法。先序遍历。利用了根节点的值，比左子树所有节点都大，比右子树所有节点都小的性质。
class Solution {
public:
bool isValidBST(TreeNode* root) {
return helper(root, LONG_MIN, LONG_MAX);
}
bool helper(TreeNode* root, long minVal, long maxVal) {
if (!root) return true;
if (root->val >= maxVal || root->val <= minVal) return false;
return helper(root->left, minVal, root->val) && helper(root->right, root->val, maxVal);
}
};
109. Convert Sorted List to Binary Search Tree
- 根据有序链表生成平衡二叉搜索树。
- 先序遍历，找出链表中点作为root节点。
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if (!head) return NULL;
ListNode preHead = ListNode(0);
preHead.next = head;
ListNode *twoStep = head, *mid = head, *preMid = &preHead;
while (mid && twoStep && twoStep->next) {
preMid = preMid->next;
mid = mid->next;
twoStep = twoStep->next->next;
}
preMid->next = NULL;
TreeNode *node = new TreeNode(mid->val);
node->left = sortedListToBST(preHead.next);
node->right = sortedListToBST(mid->next);
return node;
}
};
100. Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
- 比较2棵树是否相同，dfs，先序遍历且左右子树同时遍历。
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p || !q) {
if (!p && !q) return true;
else return false;
}
if (p -> val != q -> val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
- 审题要仔细，这个是要求是否是镜像二叉树，即是左右对称的。
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return comp(root->left, root->right);
}
bool comp(TreeNode* left, TreeNode* right) {
if (!left && !right) return true;
else if(!left || !right) return false;
return comp(left->left, right->right) && comp(left->right, right->left);
}
105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
- 节点值不重复，根据先序遍历结果和中序遍历结果构造出树。思路很清晰，先序第一个为root，再到中序找root节点，左边的为左子树，右边的为右子树。（实现起来有点恶心）
- 已知后序和中序构造树的情况差不多，后序的最后一个节点为root节点。
- 要确定树的结果必须有中序，如果只有先序和后序是无法区分左右子树的。
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
return create(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
TreeNode* create(vector<int>& preorder, vector<int>& inorder, int ps, int pe, int is, int ie){
if(ps > pe){
return nullptr;
}
TreeNode* node = new TreeNode(preorder[ps]);
int pos;
for(int i = is; i <= ie; i++){
if(inorder[i] == node->val){
pos = i;
break;
}
}
node->left = create(preorder, inorder, ps + 1, ps + pos - is, is, pos - 1);
node->right = create(preorder, inorder, pe - ie + pos + 1, pe, pos + 1, ie);
return node;
}
113. Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For 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]
]
- 求全部从根节点到叶子节点val之和为sum的情况。
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
if (!root) return res;
pathSum(root, sum, res, {});
return res;
}
void pathSum(TreeNode* root, int sum, vector<vector<int>> &res, vector<int> cur) {
if (!root) return;
sum -= root->val;
cur.push_back(root->val);
if (!root->left && !root->right) {
if (!sum) res.push_back(cur);
return;
}
pathSum(root->left, sum, res, cur);
pathSum(root->right, sum, res, cur);
}
129. Sum Root to Leaf Numbers
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.
For 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.
- 返回从根节点到叶子节点代表数值的和。注意preorder中的对root为空时，返回0。此时对应的情况为只是存在一边子树的情况。
int sumNumbers(TreeNode* root) {
if (!root) return 0;
return preorder(root, 0);
}
int preorder(TreeNode* root, int val) {
if (!root) return 0;
val = val*10 + root->val;
if (!root->left && !root->right) return val;
return preorder(root->left, val) + preorder(root->right, val);
}
99. Recover Binary Search Tree
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?
- 利用了二叉搜索树的有序特点，中序遍历会得到拍好序的结果。
6, 3, 4, 5, 2
We compare each node with its next one and we can find out that 6 is the first element to swap because 6 > 3 and 2 is the second element to swap because 2 < 5.
要注意遍历的left、right的取值，left取prev，right取root。
class Solution {
public:
void recoverTree(TreeNode* root) {
inorder(root);
if (left && right) {
swap(left->val, right->val);
}
}
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left);
if (!left && prev->val >= root->val) left = prev;
if (left && prev->val >= root->val) right = root;
prev = root;
inorder(root->right);
}
private:
TreeNode* left = NULL;
TreeNode* right = NULL;
TreeNode* prev = new TreeNode(INT_MIN);
};
110. Balanced Binary Tree
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.
- 求二叉树是否是平衡二叉树，左右深度差不超过1
// 方法1：时间复杂度$O(n\log n)$，每次遍历求该点的深度。
int getDepth(TreeNode* root) {
if (!root) return 0;
return max(getDepth(root->left), getDepth(root->right)) + 1;
}
bool isBalanced(TreeNode* root) {
if (!root) return true;
int left = getDepth(root->left);
int right = getDepth(root->right);
return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
// 方法2：时间复杂度$O(n)$，返回值为int，用-1来标记不成功。
int getDFSDepth(TreeNode* root) {
if (!root) return 0;
int left = getDFSDepth(root->left);
if (left == -1) return -1;
int right = getDFSDepth(root->right);
if (right == -1) return -1;
if (abs(left-right) > 1) return -1;
return max(left, right) + 1;
}
bool isBalanced(TreeNode* root) {
return getDFSDepth(root) != -1;
}
124. Binary Tree Maximum Path Sum
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.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
- 这道题目的意思是求连城一条线的最大和（因为可能有节点值为负，所以可能是中断的）。
- 每个节点为root的情况为，maxSum = max(maxSum, left + right + node->val)。其中left、right均大于等于0。
int maxPathSum(TreeNode* root) {
int maxValue = INT_MIN;
maxPathDown(root, maxValue);
return maxValue;
}
int maxPathDown(TreeNode* node, int &maxValue) {
if (node == nullptr) return 0;
int left = max(0, maxPathDown(node->left, maxValue));
int right = max(0, maxPathDown(node->right, maxValue));
maxValue = max(maxValue, left + right + node->val);
return max(left, right) + node->val;
}
114. Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
- 将二叉树按照先序遍历的顺序重新构造成链表。根左右=>右左根，从结果序列的后面往前遍历，记录上一个并将right指向上一个。
class Solution {
public:
void flatten(TreeNode* root) {
if (!root) return;
flatten(root->right);
flatten(root->left);
root->right = prev;
root->left = NULL;
prev = root;
}
private:
TreeNode* prev = NULL;
};
102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
- 从顶到底，从左到右依次输出节点值。和层序遍历的主要区别是，记录每层节点个数，依次取出。
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
while (!nodeQueue.empty()) {
auto level = nodeQueue.size();
res.push_back(vector<int>());
for (auto i = 0; i < level; ++i) {
TreeNode* node = nodeQueue.front();
nodeQueue.pop();
res[res.size() - 1].push_back(node->val);
if (node->left) nodeQueue.push(node->left);
if (node->right) nodeQueue.push(node->right);
}
}
return res;
}
103. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
- BFS。使用队列记录遍历过的点，每次循环更新队列中节点为树某一层节点。需要注意每次循环开始时，记录当前队列节点个数，本次循环取出全部该个数节点。
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root) return vector<vector<int>>();
vector<vector<int>> res;
bool left2right = true;
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
while (!nodeQueue.empty()) {
int queueSize = nodeQueue.size();
vector<int> row(queueSize);
for (int i = 0; i < queueSize; ++i) {
TreeNode *node = nodeQueue.front();
nodeQueue.pop();
int index = left2right ? i : queueSize - 1 - i;
row[index] = node->val;
if (node->left) nodeQueue.push(node->left);
if (node->right) nodeQueue.push(node->right);
}
left2right = !left2right;
res.push_back(row);
}
return res;
}
116. Populating Next Right Pointers in Each Node
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.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For 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
- 将二叉树使用next指针连接起来
void connect(TreeLinkNode *root) {
if (!root) return;
queue<TreeLinkNode*> nodeQueue;
nodeQueue.push(root);
while (!nodeQueue.empty()) {
auto level = nodeQueue.size();
for (auto i = 0; i < level; ++i) {
TreeLinkNode* node = nodeQueue.front();
nodeQueue.pop();
if (i == level - 1) node->next = NULL;
else node->next = nodeQueue.front();
if (node->left) nodeQueue.push(node->left);
if (node->right) nodeQueue.push(node->right);
}
}
}