- https://leetcode-cn.com/problems/Validate-Binary-Search-Tree/">验证二叉搜索树 https://leetcode-cn.com/problems/Validate-Binary-Search-Tree/
- https://leetcode-cn.com/problems/Binary-Tree-Inorder-Traversal/">二叉树的中序遍历 https://leetcode-cn.com/problems/Binary-Tree-Inorder-Traversal/
- https://leetcode-cn.com/problems/binary-tree-postorder-traversal/">二叉树的后序遍历 https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
- https://leetcode-cn.com/problems/binary-tree-preorder-traversal/">二叉树的前序遍历 https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
- https://leetcode-cn.com/problems/Symmetric-Tree/">对称二叉树 https://leetcode-cn.com/problems/Symmetric-Tree/
- https://leetcode-cn.com/problems/Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal/">从前序与中序遍历序列构造二叉树 https://leetcode-cn.com/problems/Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal/
- https://leetcode-cn.com/problems/Binary-Tree-Level-Order-Traversal/">二叉树的层次遍历 https://leetcode-cn.com/problems/Binary-Tree-Level-Order-Traversal/
- https://leetcode-cn.com/problems/Lowest-Common-Ancestor-of-a-Binary-Tree/">二叉树的最近公共祖先 https://leetcode-cn.com/problems/Lowest-Common-Ancestor-of-a-Binary-Tree/
- https://leetcode-cn.com/problems/Diameter-of-Binary-Tree/">二叉树的直径 https://leetcode-cn.com/problems/Diameter-of-Binary-Tree/
- https://leetcode-cn.com/problems/Binary-Tree-Maximum-Path-Sum/">二叉树中的最大路径和 https://leetcode-cn.com/problems/Binary-Tree-Maximum-Path-Sum/
- https://leetcode-cn.com/problems/Binary-Search-Tree-Iterator/">二叉搜索树迭代器 https://leetcode-cn.com/problems/Binary-Search-Tree-Iterator/
- https://leetcode-cn.com/problems/Serialize-and-Deserialize-Binary-Tree/">二叉树的序列化与反序列化 https://leetcode-cn.com/problems/Serialize-and-Deserialize-Binary-Tree/
树
验证二叉搜索树 https://leetcode-cn.com/problems/Validate-Binary-Search-Tree/
class Solution {
public:
bool isValidBST(TreeNode* root) {
typedef long long ll;
function<bool (TreeNode*, ll, ll)> f = [&](TreeNode *root, ll min_val, ll max_val) -> bool {
if (!root) return true;
if (root->val >= min_val && root->val <= max_val) return f(root->left, min_val, root->val - 1ll) && f(root->right, root->val + 1ll, max_val);
return false;
};
return f(root, INT_MIN, INT_MAX);
}
};
大概思路:确定每棵树的 值范围
二叉树的中序遍历 https://leetcode-cn.com/problems/Binary-Tree-Inorder-Traversal/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
auto s = stack<TreeNode*>();
auto vec = vector<int>();
auto p = root;
while (p || s.size()) {
while (p) s.push(p), p = p->left;
p = s.top(); s.pop();
vec.push_back(p->val);
p = p->right;
}
return vec;
}
};
二叉树的后序遍历 https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> ans;
auto p = root;
while (p || s.size()) {
while (p) {
s.push(p);
ans.push_back(p->val);
p = p->right;
}
p = s.top(); s.pop();
p = p->left;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
二叉树的前序遍历 https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
auto p = root;
stack<TreeNode*> s;
while (p || s.size()) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top(); s.pop();
p = p->right;
}
return ans;
}
};
三种遍历思路都差不多,利用 stack 去存递归回来会访问的点,后序遍历有点特殊,整个结果反了一下
对称二叉树 https://leetcode-cn.com/problems/Symmetric-Tree/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
stack<TreeNode*> s1, s2;
auto p = root->left, q = root->right;
while ( (p || s1.size()) && (q || s2.size()) ) {
while (p && q) {
s1.push(p); p = p->left;
s2.push(q); q = q->right;
}
if (p || q) return false;
p = s1.top(); s1.pop();
q = s2.top(); s2.pop();
if (p->val != q->val) return false;
p = p->right;
q = q->left;
}
return true;
}
bool f(TreeNode *left, TreeNode *right) {
if (!left || !right) return left == right;
return left->val == right->val && f(left->left, right->right) && f(left->right, right->left);
}
};
大概思路:
递归写法比较简单
非递归写法是这样,还是利用前面非递归实现树的遍历去做,只是左右两边反着来,左边是先左,右边是先右
从前序与中序遍历序列构造二叉树 https://leetcode-cn.com/problems/Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal/
class Solution {
public:
unordered_map<int, int> m;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// 前序遍历找根,中序遍历确定子树
int n = preorder.size();
for (int i = 0; i < n; i++) m[inorder[i]] = i;
return f(preorder, 0, 0, preorder.size() - 1);
}
TreeNode* f(const vector<int> & pre_o, int p, int l, int r) {
if (l > r) return NULL;
auto root = new TreeNode(pre_o[p]);
int pos = m[pre_o[p]];
root->left = f(pre_o, p + 1, l, pos - 1);
root->right = f(pre_o, p + pos - l + 1,pos + 1, r);
return root;
}
};
大概思路:前序遍历时,子树一定在根右边,中序遍历时,左子树在根左边,右子树在根右边
用哈希表优化一下,这样在中序遍历里找根时,可以不用扫过去,使总的复杂度是 O(N)
二叉树的层次遍历 https://leetcode-cn.com/problems/Binary-Tree-Level-Order-Traversal/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
queue<TreeNode*> q;
if (root) q.push(root);
while (q.size()) {
int len = q.size();
vector<int> sub;
while (len--) {
auto node = q.front(); q.pop();
sub.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ans.push_back(sub);
}
return ans;
}
};
大概思路:bfs过去就行,不过可以用一个小技巧,每次拿一层节点出来,从而少几个变量
队列里一共有 N 个元素,说明这一层只需要扩展 N 次,每一层都按照这样弄,自然就是一次扩展一层。
二叉树的最近公共祖先 https://leetcode-cn.com/problems/Lowest-Common-Ancestor-of-a-Binary-Tree/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return root;
if (root == p || root == q) return root;
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if (!left) return right;
if (!right) return left;
return root;
// 总共有三种情况
// p 是 q 的父节点
// q 是 p 的父节点
// p 和 q 有一个最近公共节点
/*
1 和 2 都能表现为 在一边找到了 p/q,而另一边为空
3 能表现为,在两边各自找到了 p/q,所以答案一定是 root
*/
}
};
大概思路:由于并不没有什么时间复杂度的限制,所以简单点写就好。
一棵树的最近公共祖先:
- 在左子树上
- 在右子树上
- 根节点
如果一棵树 根节点p || 根节点q,那么返回根节点
如果一棵树,左子树递归解决,记作 left,右子树递归解决,记作 right
如果 left 和 right 只有一个为空,那么另一个一定不是空的点一定是最近公共祖先
如果 left 和 right 都为空,那么返回根节点
二叉树的直径 https://leetcode-cn.com/problems/Diameter-of-Binary-Tree/
class Solution {
public:
int ans = 0;
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode *root) {
if (!root) return 0;
int l = dfs(root->left);
int r = dfs(root->right);
ans = max(ans, l + r);
return max(l, r) + 1;
}
};
大概思路,枚举当前子树的最大值,更新答案,并把当前子树的最大深度返回上一层
二叉树中的最大路径和 https://leetcode-cn.com/problems/Binary-Tree-Maximum-Path-Sum/
class Solution {
public:
int ans = INT_MIN;
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode *root) {
if (!root) return 0;
int left = dfs(root->left);
int right = dfs(root->right);
ans = max(ans, left + right + root->val);
return max(0, max(left, right) + root->val);
}
};
大概思路:和上题思路一样,不过这里有一点要注意。如果当前子树的最大值小于 0,那么就不用往上返回了。上面不会用到。
二叉搜索树迭代器 https://leetcode-cn.com/problems/Binary-Search-Tree-Iterator/
class BSTIterator {
public:
stack<TreeNode*> s;
TreeNode *p;
BSTIterator(TreeNode* root) {
p = root;
while (p) {
s.push(p);
p = p->left;
}
}
/** @return the next smallest number */
int next() {
p = s.top(); s.pop();
int val = p->val;
p = p->right;
while (p) {
s.push(p);
p = p->left;
}
return val;
}
/** @return whether we have a next smallest number */
bool hasNext() {
return s.size();
}
};
大概思路:和上面一样,不过是把非递归遍历分开了写
二叉树的序列化与反序列化 https://leetcode-cn.com/problems/Serialize-and-Deserialize-Binary-Tree/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string ans;
dfs(root, ans);
// cout << ans << endl;
return ans.substr(1);
}
void dfs(TreeNode *root, string &ans) {
if (!root) {
ans += ",#";
return;
}
ans += "," + to_string(root->val);
dfs(root->left, ans);
dfs(root->right, ans);
}
int myatoi(int &pos, const string & str) {
bool isMinus = false;
int s = 0;
if (str[pos] == '-') isMinus = true, pos++;
while (str[pos] != ',') {
s = s * 10 + str[pos] - '0';
pos++;
}
pos++;
return isMinus ? s * -1 : s;
}
TreeNode* dfs2(int &pos, const string & data) {
if (data[pos] == '#') {
pos += 2;
return NULL;
}
auto head = new TreeNode(myatoi(pos, data));
head->left = dfs2(pos, data);
head->right = dfs2(pos, data);
return head;
}
TreeNode* deserialize(string data) {
int pos = 0;
return dfs2(pos, data);
}
};
大概思路:虽然前序遍历不能确认一棵树,但前序遍历加记录空节点可以
有一点需要注意,传进函数里的 pos 是能动的,使得下一个调用完下一个函数之后,上一层可以利用当前层的信息,直接往下,节省时间。