算法训练营|226.翻转二叉树、101.对称二叉树、104.二叉树的最大深度和111.二叉树的最小深度
昨日回顾 226.翻转二叉树 卡哥文字以及视频讲解链接 重点 c++实现 （递归） 前序 c++实现 （迭代） 中序 c++实现 （统一迭代） 前序 c++实现 （层序） 101.对称二叉树
104.二叉树的最大深度 卡哥文字以及视频讲解链接 重点 c++实现 （递归、后序） c++实现 （递归、后序）优化版，其实就是少几个自定义变量 c++实现 （递归、前序） c++实现 （层序） 111.二叉树的最小深度 卡哥文字以及视频讲解链接 重点 c++实现 （前序）递归 c++实现 （前序）迭代 坚持就是胜利
昨日回顾
二叉树的链式构造方式和链表类似，通过数据域和指针域来实现。 二叉树的迭代遍历如果使用单一的容器适配器来实现，那循环遍历的条件就是判断适配器是否为空，循环内部的函数体要使用的对象要在循环开始处获得，就是栈顶或队列头部的元素。 如果需要辅助指针来实现，那循环遍历的条件就是判断适配器是否为空，以及指针是否为空。 226.翻转二叉树
卡哥文字以及视频讲解链接
重点
递归实现。前序后序实现几乎一样，中序因为是在左反转之后交换左右子树，所以后续还是反转左侧。 迭代实现。 统一迭代。 层序遍历。 这道题本质就是遍历，昨天熟悉代码，今天掌握代码。 c++实现 （递归） 前序
class Solution {
public :
TreeNode* invertTree ( TreeNode* root) {
if ( root == nullptr ) return root;
swap ( root -> left, root -> right) ;
if ( root -> left) invertTree ( root -> left) ;
if ( root -> right) invertTree ( root -> right) ;
return root;
}
} ;
c++实现 （迭代） 中序
class Solution {
public :
TreeNode* invertTree ( TreeNode* root) {
stack< TreeNode* > st;
TreeNode* cur = root;
while ( ! st. empty ( ) || cur != nullptr ) {
if ( cur) {
st. push ( cur) ;
cur = cur -> left;
} else {
cur = st. top ( ) ;
st. pop ( ) ;
swap ( cur -> left, cur -> right) ;
cur = cur -> left;
}
}
return root;
}
} ;
c++实现 （统一迭代） 前序
class Solution {
public :
TreeNode* invertTree ( TreeNode* root) {
stack< TreeNode* > st;
if ( root != nullptr ) st. push ( root) ;
while ( ! st. empty ( ) ) {
TreeNode* temp = st. top ( ) ;
if ( temp) {
st. pop ( ) ;
if ( temp -> right) st. push ( temp -> right) ;
if ( temp -> left) st. push ( temp -> left) ;
st. push ( temp) ;
st. push ( nullptr ) ;
} else {
st. pop ( ) ;
temp = st. top ( ) ;
st. pop ( ) ;
swap ( temp -> left, temp -> right) ;
}
}
return root;
}
} ;
c++实现 （层序）
class Solution {
public :
TreeNode* invertTree ( TreeNode* root) {
queue< TreeNode* > que;
if ( root != nullptr ) que. push ( root) ;
while ( ! que. empty ( ) ) {
int size = que. size ( ) ;
for ( int i = 0 ; i < size ; i++ ) {
TreeNode* temp = que. front ( ) ;
que. pop ( ) ;
if ( temp -> left) que. push ( temp -> left) ;
swap ( temp -> left, temp -> right) ;
if ( temp -> left) que. push ( temp -> left) ;
}
}
return root;
}
} ;
101.对称二叉树
卡哥文字以及视频讲解链接
重点
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树 （这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。 c++实现 （递归）
class Solution {
public :
bool isSymmetric ( TreeNode* root) {
if ( root == nullptr ) return true ;
return compareTreenode ( root -> left, root -> right) ;
}
bool compareTreenode ( TreeNode* left, TreeNode* right) {
if ( ( left == nullptr && right != nullptr ) ||
( left != nullptr && right == nullptr ) ) return false ;
else if ( left == nullptr && right == nullptr ) return true ;
else if ( left -> val != right -> val) return false ;
bool outside = compareTreenode ( left -> left, right -> right) ;
bool inside = compareTreenode ( left -> right, right -> left) ;
return outside && inside;
}
} ;
c++实现 （迭代）栈
class Solution {
public :
bool isSymmetric ( TreeNode* root) {
if ( root == nullptr ) return true ;
stack< TreeNode* > st;
st. push ( root -> left) ;
st. push ( root -> right) ;
while ( ! st. empty ( ) ) {
TreeNode* temp1 = st. top ( ) ;
st. pop ( ) ;
TreeNode* temp2 = st. top ( ) ;
st. pop ( ) ;
if ( ( temp1 == nullptr && temp2 != nullptr ) ||
( temp1 != nullptr && temp2 == nullptr ) ) return false ;
else if ( temp1 == nullptr && temp2 == nullptr ) continue ;
else if ( temp1 -> val != temp2 -> val) return false ;
st. push ( temp1 -> left) ;
st. push ( temp2 -> right) ;
st. push ( temp1 -> right) ;
st. push ( temp2 -> left) ;
}
return true ;
}
} ;
104.二叉树的最大深度
卡哥文字以及视频讲解链接
重点
都是在遍历基础上的改进 层序最容易理解的，递归代码最简洁 前序是「边走边记」，后序是「回溯汇总」 c++实现 （递归、后序）
class Solution {
public :
int maxDepth ( TreeNode* root) {
if ( root == nullptr ) return 0 ;
int leftDepth = maxDepth ( root -> left) ;
int rightDepth = maxDepth ( root -> right) ;
return 1 + max ( leftDepth, rightDepth) ;
}
} ;
c++实现 （递归、后序）优化版，其实就是少几个自定义变量
class Solution {
public :
int maxDepth ( TreeNode* root) {
if ( root == nullptr ) return 0 ;
return 1 + max ( maxDepth ( root-> left) , maxDepth ( root-> right) ) ;
}
} ;
c++实现 （递归、前序）
class Solution {
public :
int maxDepth ( TreeNode* root) {
if ( ! root) return 0 ;
int depth = 0 ;
getDepth ( root, depth, 1 ) ;
return depth;
}
void getDepth ( TreeNode* root, int & depth, int pre) {
if ( ! root) return ;
depth = max ( depth, pre) ;
getDepth ( root-> left, depth, pre + 1 ) ;
getDepth ( root-> right, depth, pre + 1 ) ;
return ;
}
} ;
c++实现 （层序）
class Solution {
public :
int maxDepth ( TreeNode* root) {
if ( root == nullptr ) return 0 ;
queue< TreeNode* > que;
que. push ( root) ;
int count = 0 ;
while ( ! que. empty ( ) ) {
int size = que. size ( ) ;
count++ ;
int j = 0 ;
for ( int i = 0 ; i < size ; i++ ) {
TreeNode* temp = que. front ( ) ;
que. pop ( ) ;
if ( temp -> left) que. push ( temp -> left) ;
if ( temp -> right) que. push ( temp -> right) ;
}
}
return count;
}
} ;
111.二叉树的最小深度
卡哥文字以及视频讲解链接
重点
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。 叶子节点，左右孩子都为空的节点才是叶子节点！ c++实现 （前序）递归
class Solution {
private :
int result;
void getdepth ( TreeNode* node, int depth) {
if ( node == nullptr ) {
return ;
}
if ( node -> left == nullptr && node-> right == nullptr ) {
result = min ( result, depth) ;
}
if ( node-> left) {
getdepth ( node-> left, depth + 1 ) ;
}
if ( node-> right) {
getdepth ( node-> right, depth + 1 ) ;
}
return ;
}
public :
int minDepth ( TreeNode* root) {
if ( root == nullptr ) {
return 0 ;
}
result = INT_MAX;
getdepth ( root, 1 ) ;
return result;
}
} ;
c++实现 （前序）迭代
class Solution {
public :
int minDepth ( TreeNode* root) {
if ( ! root) return 0 ;
stack< pair< TreeNode* , int >> st;
st. push ( { root, 1 } ) ;
int minDep = INT32_MAX;
while ( ! st. empty ( ) ) {
auto [ temp, d] = st. top ( ) ;
st. pop ( ) ;
if ( ! temp-> left && ! temp-> right) {
minDep = min ( minDep, d) ;
continue ;
}
if ( temp-> right) st. push ( make_pair ( temp-> right, d+ 1 ) ) ;
pair x{ temp-> left, d+ 1 } ;
if ( temp-> left) st. push ( x) ;
}
return minDep;
}
} ;
坚持就是胜利
日期 天次 题目 01-27 14 226、101、104、111
author
轩
