1. 二叉树的链表存储结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
2.二叉树的遍历
先序遍历(Pre-Order Traversal)：根结点->左子树->右子树
中序遍历(In-Order Traversal)：左子树->根结点->右子树
后序遍历(Post-Order Traversal)：左子树->右子树->根结点
2.1 Pre-Order Traversal
[https://www.youtube.com/watch?v=fgEZMCrFrt4&list=PLe68gYG2zUeVNPEr9XPqeejGHihtQD6tl&index=12]
Leetcode 144 https://leetcode.com/problems/binary-tree-preorder-traversal/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if(root == NULL) return{};
res.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
return res;
}
private:
vector<int> res;
};
2.2 In-Order Traversal
Leetcode 94 https://leetcode.com/problems/binary-tree-inorder-traversal/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if(root == NULL) return{};
inorderTraversal(root->left);
res.push_back(root->val);
inorderTraversal(root->right);
return res;
}
private:
vector<int> res;
};
2.3 Post-Order Traversal
Leetcode 145 https://leetcode.com/problems/binary-tree-postorder-traversal/
2.4 用堆栈来实现非递归方式中序遍历，先序遍历
Leetcode 94 https://leetcode.com/problems/binary-tree-inorder-traversal/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode* > tree_stack;
TreeNode* T = root;
vector<int> res;
while(T !=NULL || !tree_stack.empty()){
while(T != NULL){
tree_stack.push(T);
T = T->left;
}
if(!tree_stack.empty()){
T = tree_stack.top();
tree_stack.pop();
res.push_back(T->val);
T = T->right;
}
}
return res;
}
};
中序遍历的时候，是第二次碰到根结点，输出根结点的值，而先序遍历时，是第一次碰到根结点的时候就输出。因此只用在代码里面改一下输出代码的位置就好！（真的很佩服浙大这个老师，总结的太好了，本ppt视频链接位于第一张图的下方）
2.5层序遍历：从上到下，从左到右
队列实现：遍历从根结点开始，首先将根结点入队，然后执行循环；结点出队，访问该结点，左右儿子入队
Leetcode 102https://leetcode.com/problems/binary-tree-level-order-traversal/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(root == NULL) return {};
vector<vector<int> > res;
queue<TreeNode *> myQ;
myQ.push(root);
TreeNode* p;
int cnt;
while(!myQ.empty()){
vector<int> _level;
cnt = myQ.size();
while(cnt--){
p = myQ.front();
myQ.pop();
// cout<< typeid(p->left).name() << endl;
if(p->left) myQ.push(p->left);
if(p->right) myQ.push(p->right);
_level.push_back(p->val);
}
res.push_back(_level);
}
return res;
}
};
2.6由二叉树遍历引申得到的例题
2.6.1 输出二叉树中的叶子结点
2.6.2 求二叉树的高度
在后序遍历的代码中改的
Leetcode 104 https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root) return 0;
return max(maxDepth(root->left), maxDepth(root->right))+1;
}
};
2.6.3 分裂二叉树的最大积（LeetCode1339）
- 像这种将total分成两部分的题目，被剪掉的部分和为res，那么乘积为res*(total-res)。所以需要计算出所有结点的和，以及从下往上每个父节点的和。
- 为了得到从下往上每个父节点和，这里要采用后序遍历的方式（因为根结点最后遍历），所以可以套用后序遍历的递归模板，计算每个父节点的值（left+right+root->val）.
class Solution {
public:
int maxProduct(TreeNode* root) {
if(!root) return 0;
total = postOrderTraversal(root);
maxSum(root);
return bias % mod;
}
private:
long long int total = 0, bias = 0, mod = pow(10,9)+7;
long long int postOrderTraversal(TreeNode* root){
if(!root) return 0;
long long int left = postOrderTraversal(root->left);
long long int right = postOrderTraversal(root->right);
long long int sum = left + right + root->val;
return sum;
}
long long int maxSum(TreeNode* root){
if(!root) return 0;
long long int left = maxSum(root->left);
long long int right = maxSum(root->right);
long long int sum = left + right + root->val;
bias = max(bias, sum * (total-sum));
return sum;
}
};
*剑指offer：树的子结构（输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构））
如上图所示，分成两步：
- 在树A种递归找到与树B根节点值一样的节点R（实际上就是树的遍历）,满足条件的可以进行第二步。
- 再判断树A中以节点R为根结点的树是否包含树B的结构。同样利用递归的思路，如果节点R的值与树B的根结点不相同，那么直接返回false，如果相同则递归的判断节点R的左右节点和树B根结点的左右节点是否相同，终止条件是我们到达了树Ａ或者树B的叶节点，当树B为空时，直接返回true，当树A为空，树B不为空，则直接返回false。
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(!pRoot2) return false;
if(!pRoot1 && pRoot2) return false;
bool res = false;
if(pRoot1->val == pRoot2->val){
res = helper(pRoot1, pRoot2);
}
if(!res){
res = HasSubtree(pRoot1->left, pRoot2);
if(!res){
res = HasSubtree(pRoot1->right, pRoot2);
}
}
return res;
}
bool helper(TreeNode* pRoot1, TreeNode* pRoot2){
if(!pRoot2) return true;
if(!pRoot1 && pRoot2) return false;
if(pRoot1->val == pRoot2->val){
return helper(pRoot1->left, pRoot2->left) && helper(pRoot1->right, pRoot2->right);
}
else{
return false;
}
}
};
3. 2020/09/14 美团面试题 Leetcode 124 二叉树的最大路径和
https://leetcode.com/problems/binary-tree-maximum-path-sum/
class Solution {
public:
int maxPathSum(TreeNode* root) {
if(root == NULL)
return 0;
dfs(root);
return max_path_sum;
}
int dfs(TreeNode* root){
if(root == NULL)
return 0;
// 如果左边是负数，那么就不需要了，设为0
int leftMax = max(0, dfs(root->left));
int rightMax = max(0, dfs(root->right));
// left+root+right的值与历史最大值比较，更新历史最大值
max_path_sum = max(max_path_sum, root->val + leftMax + rightMax);
// 返回root的最大单边分支（左还是右）给上游
return root->val+max(leftMax, rightMax);
}
private:
int max_path_sum = INT_MIN;
};
