2专题总结-二叉树
分类:
IT文章
•
2024-01-02 15:33:48
1、 需要记忆的部分:
分治法的基本思想是将一个规模为n 的问题分解为k 个规模较小的子问题,这些子问题互相独立且与原问题相同。递归的解这些子问题,然后将各子问题的解合并得到原问题的解。
对于二叉树问题,首先需要熟练记住二叉树的前序中序遍历的递归版本和迭代版本,后序也可以看一下,记住BFS的实现过程,归并排序,快速排序,二叉搜索树BST。
完全二叉树:左右节点高度差不能超过1;
二叉搜索树:root左边的节点都小于root,root右边的节点都大于root的值。判断标准是:中序遍历是一个增序列。
AVL平衡二叉树:
总结:
1)二叉树问题基本都是考察递归,几乎所有的二叉树问题时间复杂度都是O(N),空间复杂度和二叉树的高度有关系,因为每一次递归都需要系统内存开一个栈空间进行存储,
2)其中递归函数中使用void的函数是遍历版本,使用有返回值的函数是分治版本,使用全局变量会影响多线程,
3)helper函数是在递归中使用的,因为原有的函数可能只返回一个值,而中间的递归过程需要返回多个值,此时就需要再写一个helper函数
4)在求最大值问题时候,非法情况需要些root = NULL,此时返回一个负无穷大;
再求最小值问题的时候,此时返回一个正无穷大。
写分治自己的感悟是,先想想最简单的情况是怎么写的。
二叉树问题思考过程:首先r思考递归基的情况root ==NULL,return;
然后思考左右子树递归完有什么实际意义,然后分别进行处理;
2、下面是二叉树问题的模板:
1)遍历形式的模板;
Template 1: Traverse
public class Solution {
public void traverse(TreeNode root) {
if (root == null) {
return;
}
// do something with root
traverse(root.left);
// do something with root
traverse(root.right);
// do something with root
}
}
Template 1: Traverse
2)divide and conquer模板
Tempate 2: Divide & Conquer
public class Solution {
public ResultType traversal(TreeNode root) {
// null or leaf
if (root == null) {
// do something and return;
}
// Divide
ResultType left = traversal(root.left);
ResultType right = traversal(root.right);
// Conquer
ResultType result = Merge from left and right.
return result;
}
}
View Code
注意:this是指针,谁调用struct新建变量,this就指向这个变量,它是个指针记住,所以使用->;
struct 后面接变量不加括号,最后需要加分号;,初始化方法有三种,列表初始化1,自己构造的不能使用new,再新建变量。
struct resultType{
int singlePath;
int maxPath;
// 1=> resultType(int x,int y):singlePath(x),maxPath(y){ }
// 2 => resultType(int x,int y){
// singlePath = x;
// maxPath = y;
// }
resultType(int x,int y){
this -> singlePath = x;
this -> maxPath = y;
}
};
使用new的时候必须要记得,在*分配的内存是无名的,因此new无法为其分配的对象命名,而是返回一个指向该对象的指针,所以new的时候,前面必须是指针。
resultType* result = new resultType(0,INT_MIN);//必须要加*
3、二叉树分治法题目
深度优先搜索DFS:
3.1 Lowest Common Ancestor
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/#/description
思路:需要注意接口给出的变量里面必须要有root或者parent,不然该题没法做,
1)有parent的题目,首先遍历得到两个节点的父亲节点,存在两个vector或者list中,然后分别进行遍历比较,寻找第一个不同的节点,就是所求。
2)有root的题目,使用上述模板,注意分析,该节点是root就可以直接返回,a和b节点在左右子树,则返回root,只有一个节点在二叉树中,则直接返回该节点,都不在二叉树中,则返回NULL。
注意递归基的时候,只有某个节点等于root节点,那么就已经直接返回这个节点,自己也是自己的祖先。
/**
* 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 || root == p || root == q){
return root;
}
//divide
TreeNode* leftLCA = lowestCommonAncestor(root -> left,p,q);
TreeNode* rightLCA = lowestCommonAncestor(root -> right,p,q);
//conquer
if(leftLCA != NULL && rightLCA != NULL){
return root;
}
if(leftLCA != NULL){
return leftLCA;
}
if(rightLCA != NULL){
return rightLCA;
}
return NULL;
}
};
lowest Common Ancestor
235. Lowest Common Ancestor of a Binary Search Tree
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
使用递归可以轻松解决此问题。对于此题我们可以分为三种情况讨论:
1. P, Q都比root小,则LCA在左树,我们继续在左树中寻找LCA
2. P, Q都比root大,则LCA在右树,我们继续在右树中寻找LCA
3. 其它情况,表示P,Q在root两边,或者二者其一是root,或者都是root,这些情况表示root就是LCA,直接返回root即可。
/**
* 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 || root == p || root == q){
return root;
}
if(q -> val < root -> val && p -> val < root -> val){
return lowestCommonAncestor(root -> left,p,q);
}
else if(q -> val > root -> val && p -> val > root -> val){
return lowestCommonAncestor(root -> right,p,q);
}
else{
return root;
}
}
};
Lowest Common Ancestor of a Binary Search Tree
3.2 Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/#/description
思路:递归到左右子树计算,看哪边深度大,关键理解最后一步每次返回到上一层都需要将深度增一。
根结点的深度是约定的,这道题目约定的是根节点的深度是1;根结点的深度是1,属于第1层。经过多少条边,深度就是多少。
/**
* 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);
return left > right ? left + 1 : right + 1;//关键在于这里,每次返回都使得值加1操作
}
};
max Depth
111. Minimum Depth of Binary Tree
https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
这道题是树的题目,其实跟Maximum Depth of Binary Tree非常类似,只是这道题因为是判断最小深度,所以必须增加一个叶子的判断(因为如果一个节点如果只有左子树或者右子树,我们不能取它左右子树中小的作为深度,因为那样会是0,我们只有在叶子节点才能判断深度,而在求最大深度的时候,因为一定会取大的那个,所以不会有这个问题)。这道题同样是递归和非递归的解法,递归解法比较常规的思路,比Maximum Depth of Binary Tree多加一个左右子树的判断.
/**
* 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 minDepth(TreeNode* root) {
if(root == NULL){
return 0;
}
if(root -> right == NULL){
return minDepth(root -> left) + 1;
}
if(root -> left == NULL){
return minDepth(root -> right) + 1;
}
return min(minDepth(root -> left) + 1,minDepth(root -> right) + 1);
}
};
minDepth
3.3 Balanced Binary Tree
https://leetcode.com/problems/balanced-binary-tree/#/description
思路:基于二叉树最大深度那题,当左右子树深度大于1的时候深度返回-1这步是关键
/**
* 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){//不平衡的时候用-1表示
if(root == NULL){
return 0;
}
int left = maxDepth(root -> left);
int right = maxDepth(root -> right);
if(left == -1 || right == -1 || abs(left - right) > 1){
return -1;
}
return max(left,right) + 1;
}
bool isBalanced(TreeNode* root) {
return maxDepth(root) != -1;
}
};
Balanced Binary Tree
4 宽度优先搜搜BFS
4,.1 Binary Tree Level Order Traversal (*)
https://leetcode.com/problems/binary-tree-level-order-traversal/#/description
思路:二叉树的层次遍历就是宽度优先搜索,总共有三种实现方式,
- 2 Queues(一个存parent,一个存儿子节点,每次都需要清空一个queue)
- 1 Queue + Dummy Node(每个虚拟节点代表该层结束)
- 1 Queue (best)
queue的基本操作函数:
queue默认基于deque实现,也可以使用list或者vector实现。最先入队的在右边,最先出列
q.pop(),删除最先入队的首元素,但是不返回元素的值
q.front()返回第一个入队的元素值
q.back()返回最后一个入队的值,但是不删除。
q.push()压入队列最左边元素。
这里需要注意,首先将root节点入栈,接下来是双循环,外层是队列不为空,内层是遍历每一层,进入内层循环之前要使用一个int记录队列的大小,代表该层节点个数。
还有需要注意正确释放vector内存的操作,如果使用clear函数,只会清空数组并不会释放掉系统的内存,需要使用vector<int> ().swap(vec);
/**
* 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>> result;
vector<int> tmp;
queue<TreeNode*> q;
if(root == NULL){
return result;
}
q.push(root);
while(!q.empty()){
int size = q.size();//这个是小技巧,可以得到每层的节点个数
for(int i = 0;i < size;++i){
TreeNode *node = q.front();
q.pop();
tmp.push_back(node -> val);
if(node -> left != NULL){
q.push(node -> left);
}
if(node -> right != NULL){
q.push(node -> right);
}
}
result.push_back(tmp);
tmp.clear();//记得要清空tmp数组
}
return result;
}
};
level Order
5 二叉搜索树 Binary Search Tree
5.1Validate Binary Search Tree
https://leetcode.com/problems/validate-binary-search-tree/#/description
思路:验证是否是二叉搜索树,使用中序遍历,如果是递增序列,那么就是二叉搜索树。平衡二叉树:root为空也是二叉搜索树,每个元素不相等,左边小于root,右边大于root;
/**
* 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:
void helper(TreeNode* root,vector<int>& result){
if(root != NULL){
helper(root -> left,result);
result.push_back(root ->val);
helper(root -> right,result);
}
}
bool isValidBST(TreeNode* root) {
if(root == NULL){
return true;
}
vector<int> seqInorder;//这里注意root为空的时候,seqInorder.size() - 1是一个无穷大的数字。
helper(root,seqInorder);
for(int i = 0;i < seqInorder.size() - 1;++i){
if(seqInorder[i + 1] <= seqInorder[i]){
return false;
}
}
return true;
}
};
View Code
5.2 Insert Node in a Binary Search Tree
http://www.lintcode.com/en/problem/insert-node-in-a-binary-search-tree/
思路:记住需要插入的节点一定是在二叉树某个叶子节点下面插入的(这里是理解重点),就是递归到递归基的时候,还有就是记得左右递归的if条件。
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of the binary search tree.
* @param node: insert this node into the binary search tree
* @return: The root of the new binary search tree.
*/
TreeNode* insertNode(TreeNode* root, TreeNode* node) {
// write your code here
if(root == NULL){
return node;
}
if(node -> val < root -> val){
root -> left = insertNode(root -> left,node);
}
if(node -> val > root -> val){
root -> right = insertNode(root -> right,node);
}
return root;
}
};
insert Node
5.3 Search Range in Binary Search Tree
http://www.lintcode.com/en/problem/search-range-in-binary-search-tree/
思路:注意递归的时候如果比k1大,就进入左子树,如果比k2小,就进行右子树。在两者之间,就压入result数组。
class Solution {
public:
/**
* @param root: The root of the binary search tree.
* @param k1 and k2: range k1 to k2.
* @return: Return all keys that k1<=key<=k2 in ascending order.
*/
void helper(TreeNode* root, int k1, int k2,vector<int>& result){
if(root == NULL){
return;
}
if(root -> val >= k1){
helper(root -> left,k1,k2,result);
}
if(root -> val >= k1 && root -> val <= k2){
result.push_back(root -> val);
}
if(root -> val <= k2){
helper(root -> right,k1,k2,result);
}
}
vector<int> searchRange(TreeNode* root, int k1, int k2) {
// write your code here
if(root == NULL){
return {};
}
vector<int> result;
helper(root,k1,k2,result);
// sort(result.begin(),result.end());
return result;
}
};
search Range
6.124. Binary Tree Maximum Path Sum
https://leetcode.com/problems/binary-tree-maximum-path-sum/#/description
思路:先思考一个简化版的情况,然后再思考该题。该题最大路径和可能在左子树,可能在右子树,可能是左子树的节点经过root然后到右子树的节点。
root等于空的时候是非法情况,求最大就需要返回最小,求最小就需要返回最大值。自己定义一个struct,里面包含两个值,一个是简化版的single path,一个是该题的max path。。
接下来进行分治,首先分:想左子树右子树递归完分别希望得到什么结果,接下来治:分别求出single path 和max path。
/**
* 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:
struct resultType{
int singlePath;
int maxPath;
// resultType(int x,int y):singlePath(x),maxPath(y){ }
// resultType(int x,int y){
// singlePath = x;
// maxPath = y;
// }
resultType(int x,int y){
this -> singlePath = x;
this -> maxPath = y;
}
};
resultType helper(TreeNode* root){
resultType *result = new resultType(0,INT_MIN);
if(root == NULL){
return *result;
}
//divide
resultType left = helper(root -> left);
resultType right = helper(root -> right);
//conquer
int singlePath = max(max(left.singlePath,right.singlePath) + root -> val,0);
int maxPath = max(left.maxPath,right.maxPath);
maxPath = max(maxPath,left.singlePath + right.singlePath + root -> val);
result -> singlePath = singlePath;
result -> maxPath = maxPath;
return *result;
}
int maxPathSum(TreeNode* root) {
resultType result = helper(root);
return result.maxPath;
}
};
使用new的版本
/**
* 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:
struct resultType{
int singlePath;
int maxPath;
resultType(int x,int y):singlePath(x),maxPath(y){ }
};
resultType helper(TreeNode* root){
resultType result(0,INT_MIN);
if(root == NULL){
return result;
}
//divide
resultType left = helper(root -> left);
resultType right = helper(root -> right);
//conquer
int singlePath = max(max(left.singlePath,right.singlePath) + root -> val,0);
int maxPath = max(left.maxPath,right.maxPath);
maxPath = max(maxPath,left.singlePath + right.singlePath + root -> val);
result.singlePath = singlePath;
result.maxPath = maxPath;
return result;
}
int maxPathSum(TreeNode* root) {
resultType result = helper(root);
return result.maxPath;
}
};
maxPath
7.129. Sum Root to Leaf Numbers
https://leetcode.com/problems/sum-root-to-leaf-numbers/#/description
The root-to-leaf path 1->2
represents the number 12
.
The root-to-leaf path 1->3
represents the number 13
.
Return the sum = 12 + 13 = 25
.
思路:这题还是不怎么理解,采用的是自顶向下的递归设计,所以sum = 目前值加上10倍前面的值,最后返回的时候需要将左右子树的值相加放回。因为每次都需要将sum传递给下一个递归函数,所以首先对sum进行计算,已经到达叶子节点则该路径的值以及计算出来,需要将值返回,不是叶子结点的话,就需要将左右子树的值加起来返回。
/**
* 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 helper(TreeNode* root,int sum){
if(root == NULL){
return 0;
}
sum = root -> val + sum * 10;
if(root -> left == NULL && root -> right == NULL){
return sum;
}
int left = helper(root -> left,sum);
int right = helper(root -> right,sum);
return left + right;
}
int sumNumbers(TreeNode* root) {
if(root == NULL){
return 0;
}
int sum = 0;
sum = helper(root,sum);
return sum;
}
};
sumNumbers
8.112. Path Sum
https://leetcode.com/problems/path-sum/#/description
是否存在一条路径等于指定的sum
/**
* 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 hasPathSum(TreeNode* root, int sum) {
if(root == NULL){
return false;
}
if(root -> left == NULL && root -> right == NULL){
return root -> val == sum;
}
return hasPathSum(root -> left,sum - root -> val) ||
hasPathSum(root -> right,sum - root -> val);
}
};
paht sum
9.173. Binary Search Tree Iterator
https://leetcode.com/problems/binary-search-tree-iterator/#/description
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next()
will return the next smallest number in the BST.
Note: next()
and hasNext()
should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
思路:其实就是中序遍历迭代版,这题要看清题目,是二叉搜索树,左<中<右;遍历到最左边就是最小的元素。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
public:
stack<TreeNode *> s;//全局栈
int nextMin;
BSTIterator(TreeNode *root) {
while(root != NULL){
s.push(root);
root = root -> left;
}
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !s.empty();
}
/** @return the next smallest number */
int next() {
if(!s.empty()){
TreeNode *tmp = s.top();
s.pop();
nextMin = tmp -> val;
if(tmp -> right != NULL){
TreeNode *cur = tmp -> right;
while(cur){
s.push(cur);
cur = cur -> left;
}
}
}
return nextMin;
}
};
/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
Binary Search Tree Iterator