leetcode199 二叉树的右视图
给定一个二叉树的根节点
root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
leetcode230
二叉搜索树中第 K 小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k
，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
题解
root->left->val < root->val <
root->right->val
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| int kthSmallest(TreeNode* root, int k) {
int count = 0;
stack<TreeNode*> treeStack;
treeStack.push(root);
while (treeStack.size() > 0) {
TreeNode* base = treeStack.top();
if (base->left == nullptr) {
count ++;
treeStack.pop();
if (count == k) {
return base->val;
}
if (base->right != nullptr) {
treeStack.push(base->right);
continue;
}
}
else {
treeStack.push(base->left);
base->left = nullptr;
continue;
}
}
return 0;
}
|
leetcode148 排序链表
给你链表的头结点 head ，请将其按升序排列并返回排序后的链表
题解
归并排序链表，递归分治，子链表按序合并
树和算式
Leetcode
题解
各种表达式没有本质区别，他们其实是同一个语法树，只是遍历方式不同而得到的不同式子；是一个事物的一体多面，只不过是从不同角度观察罢了。
中缀表达式是其对应的语法树的中序遍历；
后缀表达式是其对应的语法树的后序遍历；
前缀表达式是其对应的语法树的前序遍历；
leetcode105
从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder
是二叉树的先序遍历， inorder
是同一棵树的中序遍历，请构造二叉树并返回其根节点。
题解
前序遍历提供根节点，中序遍历提供子树结构
Leetcode
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
for(int i = 0; i < inorder.size(); i++)
dic[inorder[i]] = i;
return recur(0, 0, inorder.size() - 1);
}
private:
vector<int> preorder;
unordered_map<int, int> dic;
TreeNode* recur(int root, int left, int right) {
if (left > right) return nullptr;
TreeNode* node = new TreeNode(preorder[root]);
int i = dic[preorder[root]];
node->left = recur(root + 1, left, i - 1);
node->right = recur(root + i - left + 1, i + 1, right);
return node;
}
};
|
leetcode94 树的中序遍历
中序遍历
使用栈数据结构控制遍历节点顺序，类比递归调用的栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
if (root == nullptr) return ret;
stack<TreeNode*> tree;
tree.push(root);
while (! tree.empty()) {
TreeNode* top = tree.top();
if (top->left != nullptr) {
tree.push(top->left);
top->left = nullptr;
continue;
}
ret.push_back(top->val);
tree.pop();
if (top->right != nullptr) {
tree.push(top->right);
}
}
return ret;
}
};
|
通过递归重复根节点操作
leetcode124
二叉树中的最大路径和
路径
被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中
至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和
是路径中各节点值的总和。 给定一个二叉树的根节点 root ，返回其
最大路径和，即所有路径上节点值之和的最大值。
思路
共有两种路径，一种是左右节点跨越根的环形路径，一种为父子节点的直线路径
在递归的过程中，若子树的值为负，对最大和无贡献，可置为
0，计算左右子树和根节点的和，更新当前最大值
注意递归的返回值需包含根节点，已构成完整路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
private:
int maxSum = 0;
public:
int getMax(TreeNode_ root) {
if (! root) return 0;
int left = max(0, getMax(root->left));
int right = max(0, getMax(root->right));
maxSum = max(maxSum, root->val + left + right);
return root->val + max(left, right);
}
int maxPathSum(TreeNode* root) {
maxSum = INT_MIN;
getMax(root);
return maxSum;
}
};
|
完全二叉树
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第
h 层，则该层包含 1~ 2^h 个节点。
leetcode222
完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
比较有趣的思路：参考
比较左右子树高度，若相等则左子树必为满树，若不相等则右子树必为满树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int getHeight(TreeNode* root) {
if (! root) return 0;
return 1 + max(getHeight(root->left), getHeight(root->right));
}
int countNodes(TreeNode* root) {
if (! root) return 0;
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
if (leftHeight == rightHeight) {
return countNodes(root->right) + (1 << leftHeight);
}
else {
return countNodes(root->left) + (1 << rightHeight);
}
}
};
|