算法与数据结构学习笔记：二叉树
知识点
二叉树遍历
前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树 中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树 后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点
注意点
- 以根访问顺序决定是什么遍历
- 左子树都是优先右子树
前序遍历
例题：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
递归
/**
* 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:
vector<int> ans;
vector<int> preorderTraversal(TreeNode* root) {
if(root==NULL)
return ans;
// 先访问根再访问左右
ans.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
return ans;
}
};非递归
/**
* 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:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if(root==NULL)
return ans;
stack<TreeNode*> st;
TreeNode *cur=root;
while(cur!=NULL||!st.empty())
{
while(cur!=NULL)
{
ans.push_back(cur->val);
st.push(cur);
cur=cur->left;
}
cur=st.top();
st.pop();
cur=cur->right;
}
return ans;
}
};也可以这么写
/**
* 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:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if(root==NULL)
return ans;
stack<TreeNode*> st;
st.push(root);
while(!st.empty())
{
auto cur=st.top();
st.pop();
ans.push_back(cur->val);
if(cur->right)
st.push(cur->right);
if(cur->left)
st.push(cur->left);
}
return ans;
}
};中序遍历
例题：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
递归
/**
* 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:
vector<int>ans;
vector<int> inorderTraversal(TreeNode* root) {
if(root==NULL)
return ans;
inorderTraversal(root->left);
ans.push_back(root->val);
inorderTraversal(root->right);
return ans;
}
};后序遍历：
例题：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
递归：
/**
* 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:
vector<int> ans;
vector<int> postorderTraversal(TreeNode* root) {
if(root==NULL)
return ans;
postorderTraversal(root->left);
postorderTraversal(root->right);
ans.push_back(root->val);
return ans;
}
};分治法应用
先分别处理局部，再合并结果
适用场景
- 快速排序
- 归并排序
- 二叉树相关问题
分治法模板
- 递归返回条件
- 分段处理
- 合并结果
ResultType traversal(TreeNode *root) {
// nil or leaf
if (!root) {
// do something and return
}
// Divide
auto left = traversal(root->left);
auto right = traversal(root->right);
// Conquer
auto result = merge(left, right);
return result;
}典型示例
// V2：通过分治法遍历二叉树
vector<int> preOrderTraversal(TreeNode *root) {
return divideAndConquer(root);
}
vector<int> divideAndConquer(TreeNode *root) {
vector<int> result;
if (!root) {
return result;
}
// 分治(Divide)
auto left = divideAndConquer(root->left);
auto right = divideAndConquer(root->right);
// 合并结果(Conquer)
result.push_back(root->val);
result.insert(result.end(), left.begin(), left.end());
result.insert(result.end(), right.begin(), right.end());
return result;
}归并排序
template<typename T>
static void MergeSort(T arr[], int len) {
auto tmp = new T[len];
mergeSort(arr, 0, len - 1, tmp);
delete[] tmp;
}
template<typename T>
static void mergeSort(T arr[], int begin, int end, T tmp[]) {
if (begin + 1 >= end) {
return;
}
auto mid = begin + (end - begin) / 2;
auto begin1 = begin;
auto end1 = mid;
auto begin2 = mid + 1;
auto end2 = end;
mergeSort(arr, begin1, end1, tmp);
mergeSort(arr, begin2, end2, tmp);
// merge two parts
auto index = begin;
while (begin1 <= end1 && begin2 <= end2) {
tmp[index++] = arr[begin1] < arr[begin2] ? arr[begin1++] : arr[begin2++];
}
while (begin1 <= end1) {
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2) {
tmp[index++] = arr[begin2++];
}
for (int i = begin; i <= end; ++i) {
arr[i] = tmp[i];
}
}快速排序
template<typename T>
static void QuickSort(T arr[], int len) {
quickSort(arr, 0, len - 1);
}
template<typename T>
static void quickSort(T arr[], int begin, int end) {
if (begin >= end) {
return;
}
auto pivot = partition(arr, begin, end);
quickSort(arr, begin, pivot - 1);
quickSort(arr, pivot + 1, end);
}
template<typename T>
static int partition(T arr[], int begin, int end) {
auto base = arr[end];
auto lessInsert = begin;
for (int i = begin; i < end; ++i) {
if (arr[i] < base) {
swap(arr[lessInsert++], arr[i]);
}
}
swap(arr[lessInsert], arr[end]);
return lessInsert;
}常见题目示例
104. 二叉树的最大深度
/**
* 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:
int maxDepth(TreeNode* root) {
if(root==NULL)
return 0;
int left=maxDepth(root->left);
int right=maxDepth(root->right);
if(left>right)
return left+1;
else
return right+1;
}
};110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1/
2 2
/
3 3
/
4 4
返回 false 。
从底至顶
思路：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1， 因为需要返回是否平衡及高度，要么返回两个数据，要么合并两个数据， 所以用-1 表示不平衡，>0 表示树高度（二义性：一个变量有两种含义）。
注意
一般工程中，结果通过两个变量来返回，不建议用一个变量表示两种含义
/**
* 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:
bool isBalanced(TreeNode* root) {
if(maxDepth(root)==-1)
{
return false;
}
return true;
}
int maxDepth(TreeNode *root)
{
if(root==NULL)
{
return 0;
}
int left=maxDepth(root->left);
int right=maxDepth(root->right);
if(left==-1||right==-1||left-right>1||right-left>1)
{
return -1;
}
if(left>right)
{
return left+1;
}
return right+1;
}
};124. 二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
1/
2 3输出: 6
示例 2:输入: [-10,9,20,null,null,15,7]
-10
/
9 20
/
15 7输出: 42
/**
* 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:
int maxPathSum(TreeNode* root) {
int res=INT_MIN;
helper(root,res);
return res;
}
int helper(TreeNode*root,int &val)
{
if(root==NULL)
return 0;
int left=max(0,helper(root->left,val));
int right=max(0,helper(root->right,val));
int lmr=root->val+left+right;
int ret=root->val+max(left,right);
val=max(val,max(lmr,ret));
return ret;
}
};236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点
/**
* 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL)
return root;
// 相等 直接返回root节点即可
if(root==p||root==q)
return root;
auto left=lowestCommonAncestor(root->left,p,q);
auto right=lowestCommonAncestor(root->right,p,q);
// 左右两边都不为空，则根节点为祖先
if(left!=NULL&&right!=NULL)
return root;
if(left!=NULL)
return left;
if(right!=NULL)
return right;
return NULL;
}
};BFS 层次应用
102. 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
/**
* 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:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root==NULL)
return res;
queue<TreeNode *> q;
q.push(root);
while(!q.empty())
{
int currentLevelSize=q.size();
vector<int> level;
for(int i=0;i<currentLevelSize;i++)
{
auto cur=q.front();
level.push_back(cur->val);
q.pop();
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
res.push_back(level);
}
return res;
}
};107. 二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
思路：在层级遍历的基础上，翻转一下结果即可
/**
* 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:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if(root==NULL)
return res;
queue<TreeNode*>q;
q.push(root);
while(!q.empty())
{
int curLevelSize=q.size();
vector<int> curLevel;
for(int i=0;i<curLevelSize;i++)
{
auto cur=q.front();
q.pop();
curLevel.push_back(cur->val);
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
res.push_back(curLevel);
}
reverse(res.begin(),res.end());
return res;
}
};103. 二叉树的锯齿形层次遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],3
/
9 20
/
15 7
返回锯齿形层次遍历如下：[
[3],
[20,9],
[15,7]
]
思路：特定层结果翻转即可
/**
* 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:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root==NULL)
return res;
queue<TreeNode*> q;
q.push(root);
bool toggle=false;
while(!q.empty())
{
int curLevelSize=q.size();
vector<int> curLevel;
for(int i=0;i<curLevelSize;i++)
{
auto cur=q.front();
q.pop();
curLevel.push_back(cur->val);
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
if(toggle)
{
reverse(curLevel.begin(),curLevel.end());
}
toggle=!toggle;
res.push_back(curLevel);
}
return res;
}
};二叉搜索树应用
98. 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
中序遍历
/**
* 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:
bool isValidBST(TreeNode* root) {
if(root==NULL)
return true;
vector<int>res;
inOrder(root,res);
for(int i=0;i<res.size()-1;i++)
{
if(res[i]>=res[i+1])
return false;
}
return true;
}
void inOrder(TreeNode*root,vector<int> &res)
{
if(root==NULL)
return;
inOrder(root->left,res);
res.push_back(root->val);
inOrder(root->right,res);
}
};701. 二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root==nullptr)
return new TreeNode(val);
if(root->val<val)
{
root->right=insertIntoBST(root->right,val);
}
else
{
root->left=insertIntoBST(root->left,val);
}
return root;
}
};本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 陈子琦的博客！
评论