一. 树的总结
- 树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）；
1.1 常见的 DFS ： 先序遍历、中序遍历、后序遍历；
- DFS遍历：
class TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void traverse(TreeNode root){
//前序遍历
traverse(root.left)
//中序遍历
traverse(root.right)
//后序遍历
}
1.2 常见的 BFS ： 层序遍历（即按层遍历）。
- 使用队列实现。
二. Easy 题目
2.1 剑指 Offer 55 - I. 二叉树的深度
方法一：递归-深度优先-后序遍历
- 递归重点：树的深度等于 max(左子树的深度和右子树的深度) + 1.
class Solution {
public:
int maxDepth(TreeNode* root) {
return root? max(maxDepth(root->left), maxDepth(root->right))+1 : 0;
}
};
方法二：层序遍历-队列
- depth的起始值。
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root) return 0;
queue<TreeNode*> q;
q.push(root);
int depth=0;
while(q.size()>0){
int n=q.size();
for(int i=0;i<n;i++){
TreeNode* temp=q.front();
q.pop();
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
}
depth++;
}
return depth;
}
};
2.2 剑指 Offer 27. 二叉树的镜像
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(root ==NULL)
{return root;}
swap(root);
mirrorTree(root->left);
mirrorTree(root->right);
return root;
}
void swap(TreeNode* node){
TreeNode* tmp=node->left;
node->left=node->right;
node->right=tmp;
}
};
2.3 剑指 Offer 54. 二叉搜索树的第k大节点
class Solution {
public:
int kthLargest(TreeNode* root, int k) {
if(root ==NULL) return NULL;
int tree_num = TreeNum(root->right)+1;
if(tree_num == k) return root->val;
else if(tree_num < k ) return kthLargest(root->left,k-tree_num);
else return kthLargest(root->right,k);
}
int TreeNum(TreeNode* root){
if (root ==NULL) return 0;
return 1+TreeNum(root->left)+TreeNum(root->right);
}
};
- 树的中序遍历
class Solution {
public:
int kthLargest(TreeNode* root, int k) {
if(root ==NULL) return -1;
vector<int> num;
dfs(num,k,root);
return num[k-1];
}
void dfs(vector<int> &num, int &k, TreeNode* root){
if (root==NULL) return;
dfs(num,k, root->right);
if(num.size()==k) return;
num.push_back(root->val);
dfs(num,k, root->left);
}
};
2.5 剑指 Offer 32 - II. 从上到下打印二叉树 II
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if(root == NULL) return result;
queue<TreeNode*> my_queue;
my_queue.push(root);
while(!my_queue.empty()){
int depth=my_queue.size();
vector<int> tmp;
for(;depth>0;depth--){
TreeNode* top_node = my_queue.front();
my_queue.pop();
if(top_node->left)
my_queue.push(top_node->left);
if(top_node->right)
my_queue.push(top_node->right);
tmp.push_back(top_node->val);
}
result.push_back(tmp);
}
return result;
}
};
2.6 剑指 Offer 55 - II. 平衡二叉树
class Solution {
public:
bool isBalanced(TreeNode* root) {
return getDepth(root) != -1;
}
int getDepth(TreeNode* root){
if (root == NULL) return 0;
int left_depth = getDepth(root->left);
if(left_depth ==-1) return -1;
int right_depth = getDepth(root->right);
if(right_depth ==-1) return -1;
return abs(left_depth-right_depth) >1? -1:max(left_depth,right_depth)+1;
}
};
三. Medium题目
3.1 剑指 Offer 07. 重建二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size() <=0 || inorder.size()<=0 )
return NULL;
return ConstructCore(0,preorder.size()-1, 0, preorder.size()-1, preorder, inorder);
}
TreeNode* ConstructCore(int preorder_start,int preorder_end, int inorder_start,int inorder_end, vector<int>& preorder, vector<int>& inorder){
int root_value=preorder[preorder_start];
TreeNode* root=new TreeNode(root_value);
if(preorder_start == preorder_end){
if(inorder_start == inorder_end && preorder[preorder_start]==inorder[inorder_start])
return root;
}
int root_inorder=0;
while(root_inorder<inorder_end && inorder[root_inorder] != root_value){
++root_inorder;
}
int left_length=root_inorder-inorder_start;
if(left_length>0)
root->left=ConstructCore(preorder_start+1,preorder_start+left_length,inorder_start, root_inorder-1, preorder, inorder);
if(left_length < preorder_end-preorder_start)
root->right=ConstructCore(preorder_start+left_length+1,preorder_end, root_inorder+1, inorder_end, preorder, inorder);
return root;
}
};
3.2 剑指 Offer 34. 二叉树中和为某一值的路径
- 注意：很多判断条件，中间值，用减法消耗更少，避免保存中间变量。
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> result;
vector<int> one_path;
findPath(root, result, one_path, sum);
return result;
}
void findPath(TreeNode* root, vector<vector<int>>& path,vector<int> &one_path, int sum){
if (root ==NULL) return;
one_path.push_back(root->val);
sum -=root->val;
if( sum == 0 && root->left == NULL && root->right == NULL){
path.push_back(one_path);
}
if(root->left != NULL)
findPath(root->left, path, one_path, sum);
if(root->right != NULL)
findPath(root->right, path, one_path, sum);
one_path.pop_back();
}
};
- 可以声明成类的成员
class Solution {
private:
vector<vector<int>> path;
vector<int> one_path;
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
findPath(root, sum);
return path;
}
void findPath(TreeNode* root, int sum){
if (root ==NULL) return;
one_path.push_back(root->val);
sum -=root->val;
if( sum == 0 && root->left == NULL && root->right == NULL){
path.push_back(one_path);
}
if(root->left != NULL)
findPath(root->left, sum);
if(root->right != NULL)
findPath(root->right, sum);
one_path.pop_back();
}
};
3.3 剑指 Offer 26. 树的子结构
- 递归逻辑拆分合理
class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A== NULL|| B==NULL) return false;
return judgeSame(A,B) || isSubStructure(A->left,B)||isSubStructure(A->right,B);
}
bool judgeSame(TreeNode* A, TreeNode* B){
if(B==NULL )
return true;
if(A== NULL|| A->val != B->val) return false;
return judgeSame(A->left, B->left) && judgeSame(A->right, B->right);
}
};
