[TOC]
一、从数组中构造二叉树
654. 最大二叉树（中等难度）
问题：
给定一个不重复的整数数组 nums ，返回 nums 构建的 最大二叉树 :
- 创建一个根节点，其值为
nums中的最大值。 - 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
点评
分治思想：
class Solution {
public:
// 定义：输入一个数组，构建一个最大二叉树
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.size()==0)return NULL;//终止条件
/**前序位置插入**/
//寻找数组中的最大值的索引，作为切割点
int maxIndex = 0;
for(int i=0;i<nums.size();i++){
if(nums[maxIndex]<nums[i]){
maxIndex=i;
}
}
TreeNode* root=new TreeNode(nums[maxIndex]);// 构建根节点
//if(nums.size()==1)return root;//加上更加高效，终止条件
//递归调用左右子树
vector<int> leftNums(nums.begin(),nums.begin()+maxIndex);//[0,maxIndex)
root->left = constructMaximumBinaryTree(leftNums);
vector<int> rightNums(nums.begin()+maxIndex+1,nums.end());//[maxIndex+1,size)
root->right = constructMaximumBinaryTree(rightNums);
return root;
}
};
105. 从前序与中序遍历序列构造二叉树（中等难度）
剑指 Offer 07. 重建二叉树（中等难度）
问题：
点评
写法一：
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//从先序数组找切割点对应的值
if (preorder.size() == 0) return NULL;//终止条件1
int rootValue = preorder[0];
TreeNode* root = new TreeNode(rootValue);//
if (preorder.size() == 1) return root;//终止条件2
//寻找中序数组的切割点
int Index;
for (Index = 0; Index < inorder.size(); Index++) {
if (inorder[Index] == rootValue) break;
}
//切割中序数组
vector<int> leftInorder(inorder.begin(), inorder.begin() + Index);
vector<int> rightInorder(inorder.begin() + Index + 1, inorder.end() );
//寻找先序数组的切割点
Index = leftInorder.size();//长度相同
preorder.erase(preorder.begin());//删除第一个元素
//切割先序数组
vector<int> leftPreorder(preorder.begin(), preorder.begin() + Index);
vector<int> rightPreorder(preorder.begin() + Index, preorder.end());
//递归调用左右子数组
root->left = buildTree(leftPreorder,leftInorder);
root->right = buildTree(rightPreorder,rightInorder);
return root;
}
};
写法二：
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder,0, preorder.size()-1,inorder,0,inorder.size()-1);
}
TreeNode* build(vector<int>& preorder,int preStart,int preEnd, vector<int>& inorder,int inStart,int inEnd) {
if(preStart>preEnd) return nullptr;
// 前序数组的第一个节点一定是根节点
TreeNode* root=new TreeNode(preorder[preStart]);
// 在中序数组找到根节点所在索引
int index=0;
for (int i = inStart; i <= inEnd; ++i) {
if (inorder[i] == preorder[preStart]) {
index = i;
break;
}
}
// 计算左子树长度
int leftSize=index-inStart;
root->left=build(preorder,preStart+1, preStart+leftSize,inorder,inStart,index-1);
root->right=build(preorder,preStart+leftSize+1, preEnd,inorder,index+1,inEnd);
return root;
}
};
106. 从中序与后序遍历序列构造二叉树（中等难度）
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
//从后序数组找切割点对应的值
if (postorder.size() == 0) return NULL;//终止条件1
int rootValue = postorder[postorder.size()-1];//最后一个元素
TreeNode* root = new TreeNode(rootValue);
if (postorder.size() == 1) return root;//终止条件2
//寻找中序数组的切割点
int Index;
for (Index = 0; Index < inorder.size(); Index++) {
if (inorder[Index] == rootValue) break;
}
//切割中序数组
vector<int> leftInorder(inorder.begin(), inorder.begin() + Index);
vector<int> rightInorder(inorder.begin() + Index + 1, inorder.end() );
//寻找后序数组的切割点
Index = leftInorder.size();//长度相同
postorder.pop_back();//删除最后一个元素
//切割后序数组
vector<int> leftPostorder(postorder.begin(), postorder.begin() + Index);
vector<int> rightPostorder(postorder.begin() + Index, postorder.end());
//递归调用左右子数组
root->left = buildTree(leftInorder,leftPostorder);
root->right = buildTree(rightInorder,rightPostorder);
return root;
}
};
剑指 Offer 37. 序列化二叉树（困难难度）
297. 二叉树的序列化与反序列化（困难难度）
二叉树的序列化：输入一个二叉树，输出其层序遍历输出的字符串
二叉树的反序列化：输入一个字符串，输出其构造的二叉树
点评
二叉树的序列化有先序、中序、后序和层序，但是二叉树的反序列化不支持中序遍历（无法确定根节点位置）。
基于先序遍历的序列化和反序列化：
//序列化
string serialize(TreeNode* root){
string str="";
dfs(root,str);
return str;
}
void dfs(TreeNode* root,string& str){
if(root==nullptr){
str+="null,";
return;
}
str+=to_string(root->val)+",";
dfs(root->left,str);
dfs(root->right,str);
}
// 反序列化
TreeNode* deserialize(string data){
if(data.length()==0) return nullptr;
// 切割字符串
vector<string> str;
stringstream ss(data);
string t;
while(getline(ss,t,',')){
str.push_back(t);
}
// 构造二叉树
return dedfs(str,0);
}
TreeNode* dedfs(vector<string>& nodes，int i){
// 终止条件
if(i>=nodes.size()) return nullptr;
// 处理节点
if(nodes[i]=="null") return nullptr;
TreeNode* root=new TreeNode(stoi(nodes[i]));
i++;
// 递归搜索
root->left=dedfs(nodes,i);
root->right=dedfs(nodes,i);
return root;
}
基于层序遍历的序列化和反序列化：
string serialize(TreeNode* root) {
if(root==nullptr) return "";
string res="";
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
// 出栈
TreeNode* cur=que.front();
que.pop();
// 处理
if(cur==nullptr) res+="null,";
else{
res+=to_string(cur->val)+",";
// 入栈
que.push(cur->left);
que.push(cur->right);
}
}
return res;
}
TreeNode* deserialize(string data) {
if(data.length()==0) return nullptr;
// 切割字符串
vector<string> str;
stringstream ss(data);
string t;
while(getline(ss,t,',')){
str.push_back(t);
}
// 构建二叉树
queue<TreeNode*> que;
if(str[0]=="null") return nullptr;
TreeNode* root=new TreeNode(stoi(str[0]));
que.push(root);
for(int i=1;i<str.size();){
// 获取根节点
TreeNode* cur=que.front();
que.pop();
// 添加左节点
if(str[i]=="null") cur->left=nullptr;
else{
cur->left=new TreeNode(stoi(str[i]));
que.push(cur->left);
}
++i;
// 添加右节点
if(str[i]=="null") cur->right=nullptr;
else{
cur->right=new TreeNode(stoi(str[i]));
que.push(cur->right);
}
++i;
}
return root;
}
二、自顶向下遍历树
226. 翻转二叉树（简单难度）
剑指 Offer 27. 二叉树的镜像（简单难度）
问题：给你一棵二叉树的根节点 root ，水平翻转这棵二叉树，并返回其根节点。
点评
只要将二叉树的每个节点的左右子节点进行交换，就可以完全水平反转整个二叉树。
方法一：递归思想
单独抽出一个节点，需要让它把自己的左右子节点交换下
前中后序位置，似乎都可以
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
//终止条件
if (root == NULL) return root;
//处理节点
swap(root->left, root->right); // 交换左右子节点
//递归调用
mirrorTree(root->left); // 左
mirrorTree(root->right); // 右
return root;
}
};
方法二：分治思想
class Solution {
public:
// 定义：输入二叉树，返回其前序遍历数组
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(root==nullptr) return res;
// 获取左、右子树的前序遍历数组
vector<int> leftRes=preorderTraversal(root->left);
vector<int> rightRes=preorderTraversal(root->right);
// 一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果
res.push_back(root->val);
res.insert(res.end(),leftRes.begin(),leftRes.end());
res.insert(res.end(),rightRes.begin(),rightRes.end());
return res;
}
};
100. 相同的树（简单难度）
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
//终止条件
if(p==NULL&&q==NULL) return true;
else if(p!=NULL&&q==NULL) return false;
else if(p==NULL&&q!=NULL)return false;
else if(p->val!=q->val)return false;
//递归调用
bool left=isSameTree(p->left,q->left);
bool right=isSameTree(p->right,q->right);
return left&&right;
}
};
617. 合并二叉树（简单难度）
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
//终止条件
if(root1==NULL) return root2;
if(root2==NULL) return root1;
//处理节点
root1->val+=root2->val;
//递归调用
root1->left=mergeTrees(root1->left,root2->left);
root1->right=mergeTrees(root1->right,root2->right);
return root1;
}
};
101. 对称二叉树（简单难度）
剑指 Offer 28. 对称的二叉树（简单难度）
class Solution {
public:
bool compare(TreeNode* left,TreeNode* right){
//终止条件
if(left==NULL&&right==NULL) return true;
else if(left!=NULL&&right==NULL) return false;
else if(left==NULL&&right!=NULL) return false;
else if(left->val!=right->val) return false;
//递归调用
bool leftResult=compare(left->left,right->right);
bool rightResult=compare(left->right,right->left);
return leftResult&&rightResult;
}
bool isSymmetric(TreeNode* root) {
if(root==NULL) return true;
return compare(root->left,root->right);
}
};
572. 另一棵树的子树（简单难度）
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==NULL&&q==NULL)return true;
else if(p!=NULL&&q==NULL) return false;
else if(p==NULL&&q!=NULL) return false;
else if(p->val!=q->val)return false;
bool left=isSameTree(p->left,q->left);
bool right=isSameTree(p->right,q->right);
return left&&right;
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (root == NULL && subRoot == NULL) return true;//LeetCode中没有设置该情况
if (root == NULL && subRoot != NULL) return false;//LeetCode中没有设置该情况
if (root != NULL && subRoot == NULL) return false;//LeetCode中没有设置该情况
return isSameTree(root,subRoot)//root和subRoot相等
||isSubtree(root->left,subRoot)//subRoot是root的左子树的子树
||isSubtree(root->right,subRoot);//subRoot是root的右子树的子树
}
};
剑指 Offer 26. 树的子结构（中等难度）
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==NULL&&q==NULL)return true;//两个树的节点都为空，完全相等
else if(p!=NULL&&q==NULL) return true;//p的节点不为空，q的节点为空，q全部匹配p
else if(p==NULL&&q!=NULL) return false;//p的节点为空，q的节点不为空，p全部匹配q
else if(p->val!=q->val)return false;// p和q的值不一样，p和q不匹配
bool left=isSameTree(p->left,q->left);
bool right=isSameTree(p->right,q->right);
return left&&right;
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A==NULL&&B==NULL) return false;
if(A!=NULL&&B==NULL) return false;
if(A==NULL&&B!=NULL) return false;
return isSameTree(A,B)//root和subRoot相等
||isSubStructure(A->left,B)//subRoot是root的左子树的子树
||isSubStructure(A->right,B);//subRoot是root的右子树的子树
}
};
三、自顶向下计算属性
222. 完全二叉树的节点个数（中等难度）
class Solution {
public:
int countNodes(TreeNode* root) {
//终止条件
if(root==NULL)return 0;
int leftCount=countNodes(root->left);
int rightCount=countNodes(root->right);
return 1+leftCount+rightCount;
}
};
104. 二叉树的最大深度（简单难度）
剑指 Offer 55 - I. 二叉树的深度（简单难度）
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。其中根节点所在深度为1.
点评
思路一：递归思想
用一个外部变量在遍历二叉树时记录每个节点所在的深度，遇到叶节点就更新一次最大深度。
depth 记录当前递归到的节点深度，那么dfs()的前序位置就是刚进入当前节点时刻，depth+1，后序位置就是刚离开当前节点时刻，depth-1
class Solution {
public:
int res=0;
int maxDepth(TreeNode* root) {
dfs(root,1);
return res;
}
void dfs(TreeNode* root,int depth){
if(root==nullptr) return;
// （一）前序位置 depth++
// 如果达到叶节点，则达到了最大深度
if(root->left==nullptr&&root->right==nullptr) res=max(res,depth);
// 搜索两个子树方向
dfs(root->left,depth+1);
dfs(root->right,depth+1);
// （二）后序位置 depth--
}
};
思路二：分治思想
class Solution {
public:
//定义递归函数，输入一个根节点，返回其最大深度
int maxDepth(TreeNode* root) {
if(root == NULL) return 0;
// 利用定义，计算左右子树的最大深度
int leftD = maxDepth(root->left);
int rightD = maxDepth(root->right);
// 整棵树的最大深度等于左右子树的最大深度取最大值，然后再加上根节点自己
return max(leftD,rightD)+1;
}
};
559. N 叉树的最大深度（简单难度）
思路一：递归思想
class Solution {
public:
int res=0;
int maxDepth(Node* root) {
dfs(root, 1);
return res;
}
void dfs(Node* root,int depth){
if(root==nullptr) return;
// 如果达到叶节点，则达到了最大深度
if(root->children.size()==0) res=max(res, depth);
for(Node* child:root->children){
dfs(child,depth+1);
}
}
};
思路二：分治思想
class Solution {
public:
//定义递归函数，输入一个根节点，返回其最大深度
int maxDepth(Node* root) {
if(root == NULL) return 0;
int maxChild=0;
for(Node* child:root->children){
int x=maxDepth(child);// 利用定义，计算每个子树的最大深度
maxChild=max(maxChild,x);// 保存所有子树中的最大深度
}
return maxChild+1;//整个树的最大深度=所有子树中的最大深度+1
}
};
111. 二叉树的最小深度（简单难度）
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == NULL) return 0;
int leftD = minDepth(root->left);
int rightD = minDepth(root->right);
// 当只有左子树时，这时并不是最低点
if(root->left!=NULL&&root->right==NULL)return 1+leftD;
// 当只有右子树时，这时并不是最低点
if(root->left==NULL&&root->right!=NULL)return 1+rightD;
return min(leftD,rightD)+1;
}
};
543. 二叉树的直径（简单难度）
问题：给定一棵二叉树，返回它的直径长度（一棵二叉树的直径长度是任意两个结点路径长度中的最大值，这条路径可能穿过也可能不穿过根结点）。
点评
二叉树的直径=左子树的最大深度+右子树的最大深度
由于求直径，需要先求出左右子树的最大深度，所以dfs()需要后序遍历。
class Solution {
public:
/*二叉树的直径=左子树的最大深度+右子树的最大深度*/
int maxDia=0;
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return maxDia;
}
// 输入一个根节点，返回其最大深度
int dfs(TreeNode* root){
if(root==nullptr) return 0;
int leftDepth=dfs(root->left);
int rightDepth=dfs(root->right);
// 后序位置
maxDia=max(maxDia,leftDepth+rightDepth);
return 1+max(leftDepth,rightDepth);
}
};
110. 平衡二叉树（简单难度）
剑指 Offer 55 - II. 平衡二叉树（简单难度）
class Solution {
public:
//求某个节点的高度
int getHeight(TreeNode* root) {
if(root==NULL) return 0;
int leftHeight=getHeight(root->left);
int rightHeight=getHeight(root->right);
return max(leftHeight,rightHeight)+1;
}
//判断是否是平衡二叉树
bool isBalanced(TreeNode* root) {
if(root==NULL) return true;
//左子树不是平衡二叉树
if(!isBalanced(root->left)) return false;
//右子树不是平衡二叉树
if(!isBalanced(root->right)) return false;
//左右子树的高度绝对值是否小于1
int leftHeight=getHeight(root->left);
int rightHeight=getHeight(root->right);
if(abs(leftHeight-rightHeight)<=1) return true;
else return false;
}
};
三、自顶向下回溯路径
257. 二叉树的所有路径（简单难度）
class Solution {
public:
vector<string> res;
void getPaths(TreeNode* node,string path){
path+=to_string(node->val);//添加当前节点
//如果是叶子节点,说明一条路径结束,递归返回
if(node->left==nullptr&&node->right==nullptr){
res.push_back(path);
return;
}
//如果当前节点的左节点存在,递归左节点
if(node->left) getPaths(node->left,path+"->");//递归添加该节点
//如果当前节点的右节点存在,递归右节点
if(node->right) getPaths(node->right,path+"->");//递归添加该节点
}
vector<string> binaryTreePaths(TreeNode* root) {
getPaths(root,"");
return res;
}
};
112. 路径总和（简单难度）
class Solution {
public:
bool traversal(TreeNode* cur, int count) {
// 如果是叶子节点，并且为0,返回真
if (!cur->left && !cur->right && count == 0) return true;
// 如果是叶子节点，但是不为0，返回假
if (!cur->left && !cur->right) return false;
// 如果左节点存在，递归处理左节点
if (cur->left) { // 左
count -= cur->left->val; // 递归，处理节点;
if (traversal(cur->left, count)) return true;
count += cur->left->val; // 回溯，撤销处理结果
}
// 如果右节点存在，递归处理右节点
if (cur->right) { // 右
count -= cur->right->val; // 递归，处理节点;
if (traversal(cur->right, count)) return true;
count += cur->right->val; // 回溯，撤销处理结果
}
return false;
}
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == NULL) return false;
return traversal(root, targetSum - root->val);
}
};
113. 路径总和 II
剑指 Offer 34. 二叉树中和为某一值的路径
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
// 递归函数不需要返回值，因为我们要遍历整个树
void traversal(TreeNode* cur, int count) {
// 如果是叶子节点，且为0,添加到结果中并返回
if (!cur->left && !cur->right && count == 0) {
result.push_back(path);
return;
}
// 如果是叶子节点，不为0,直接返回
if (!cur->left && !cur->right) return ;
// 如果是左节点存在，递归左节点
if (cur->left) {
path.push_back(cur->left->val);
count -= cur->left->val;
traversal(cur->left, count); // 递归
count += cur->left->val; // 回溯
path.pop_back(); // 回溯
}
// 如果右节点存在，递归右节点
if (cur->right) { // 右 （空节点不遍历）
path.push_back(cur->right->val);
count -= cur->right->val;
traversal(cur->right, count); // 递归
count += cur->right->val; // 回溯
path.pop_back(); // 回溯
}
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if (root == NULL) return result;
path.push_back(root->val); // 把根节点放进路径
traversal(root, targetSum - root->val);
return result;
}
};
437. 路径总和 III（中等难度）
方法一：递归法
class Solution {
public:
// 查找包含root节点并且和为sum的路径个数
int findPath(TreeNode* root,int sum){
int result=0;
if(root==nullptr) return result;
// 如果加上root，和满足则结果+1
if(sum==root->val) result+=1;
// 查找包含root左节点
result+=findPath(root->left,sum-root->val);
// 查找包含root右节点
result+=findPath(root->right,sum-root->val);
return result;
}
// 查找包含root/不包含root并且和为targetSum的路径个数
int pathSum(TreeNode* root, int targetSum) {
int result=0;
if(root==nullptr) return result;
result+=findPath(root,targetSum);// 查找包含root节点并且和为sum的路径个数
result+=pathSum(root->left,targetSum);// 查找包含root节点并且和为sum的路径个数
result+=pathSum(root->right,targetSum);
return result;
}
};
方法二：前缀和+递归法
class Solution {
public:
unordered_map<long long, int> dict; //<[0,b]的前缀和，出现次数>
int res = 0;
// pathSum：[a,root]的目标和;curSum：[0,root]的前缀和
void dfs(TreeNode* root,int pathSum,int curSum){
if (root == nullptr) return;
curSum += root->val; //当前节点的前缀和[0,b]
// [0,b]的前缀和-[a,b]的前缀和=[0,a-1]的前缀和，哈希表中是否存在
if (dict.count(curSum - pathSum)){
res += dict[curSum - pathSum];//
}
// 将[0,b]的前缀和存入哈希表，遍历是否存在满足要求的子树
dict[curSum]++;
dfs(root->left,pathSum, curSum);//查看是否存在root的左节点的
dfs(root->right,pathSum, curSum);
// 当子树结束时，应当把子树从哈希表中移除 (回溯：将一切复原，然后结束)。
dict[curSum]--;
}
// 查找包含root/不包含root并且和为targetSum的路径个数
int pathSum(TreeNode* root, int targetSum) {
// 注意 前缀和中, [a, b] = [0, b] - [0, a-1] 。
// 对于包含根节点的路径，是无法找到 a-1 的。所以需要一个虚拟根节点。
dict[0] = 1;
dfs(root,targetSum, 0); //targetSum视为[a,b]区间的和
return res;
}
};
404. 左叶子之和（简单难度）
class Solution {
public:
int preOrder(TreeNode* root,bool isleft){
int result=0;
// 如果是空节点，返回0
if(root==NULL) return 0;
// 如果是左叶子，返回其值
if(isleft&&root->left==NULL&&root->right==NULL) return root->val;
result+=preOrder(root->left,true);// 递归左节点
result+=preOrder(root->right,false);// 递归右节点
return result;
}
int sumOfLeftLeaves(TreeNode* root) {
return preOrder(root,false);
}
};
三、自底向上寻找祖先
剑指 Offer 68 - II. 二叉树的最近公共祖先（简单难度）
236. 二叉树的最近公共祖先（中等难度）
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//如果当前节点为空，直接返回空
if(root==NULL) return NULL;
//如果当前节点值和p或者q中的一个相等，则返回当前节点
if(p->val==root->val||q->val==root->val)return root;
//递归调用
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
//如果左子树和右子树分别存在p和q
if (left != NULL && right != NULL)return root;
//如果右子树存在p和q
if (left == NULL && right != NULL)return right;
//如果左子树存在p和q
if (left != NULL && right == NULL) return left;
return NULL;
}
};