1、中序遍历
(1)题目描述以及输入输出
( 1 ) 题目描述:
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
( 2 ) 输入输出描述:
输出节点值到一个数组
关键思路:
左中右遍历
(2)代码块
class Solution {
public :
void traversal ( TreeNode* root, vector< int > & record)
{
if ( root == nullptr ) return ;
traversal ( root-> left, record) ;
record. push_back ( root-> val) ;
traversal ( root-> right, record) ;
}
vector< int > inorderTraversal ( TreeNode* root)
{
vector< int > record;
traversal ( root, record) ;
return record;
}
} ;
2、二叉树的最大深度
(1)题目描述以及输入输出
( 1 ) 题目描述:
给定一个二叉树 root ,返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
( 2 ) 输入输出描述:
输出一个最大深度
关键思路:
(2)代码块
class Solution {
public :
int getdepth ( TreeNode* root)
{
if ( root == nullptr ) return 0 ;
int leftdepth = getdepth ( root-> left) ;
int rightdepth = getdepth ( root-> right) ;
int depth = max ( leftdepth, rightdepth) + 1 ;
return depth;
}
int maxDepth ( TreeNode* root)
{
return getdepth ( root) ;
}
} ;
3、翻转二叉树
(1)题目描述以及输入输出
( 1 ) 题目描述:
给定一个二叉树 root ,翻转所有节点。
( 2 ) 输入输出描述:
关键思路:
先翻转当前节点的左右节点,
接着递归翻转子节点左右
(2)代码块
class Solution {
public :
TreeNode* invertTree ( TreeNode* root)
{
if ( root == nullptr ) return root;
swap ( root-> left, root-> right) ;
invertTree ( root-> left) ;
invertTree ( root-> right) ;
return root;
}
} ;
4、对称二叉树
(1)题目描述以及输入输出
( 1 ) 题目描述:
给你一个二叉树的根节点 root , 检查它是否轴对称。
( 2 ) 输入输出描述:
关键思路:
对于每次递归,要检查root-> left,root-> right是否对称,
因此递归函数是进行遍历检测
(2)代码块
class Solution {
public :
bool recur ( TreeNode* left, TreeNode* right)
{
if ( left == nullptr && right == nullptr ) return true ;
if ( left == nullptr || right == nullptr || left-> val != right-> val) return false ;
return recur ( left-> left, right-> right) && recur ( left-> right, right-> left) ;
}
bool isSymmetric ( TreeNode* root)
{
return root == nullptr || recur ( root-> left, root-> right) ;
}
} ;
5、二叉树的直径
(1)题目描述以及输入输出
( 1 ) 题目描述:
给你一棵二叉树的根节点,返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
( 2 ) 输入输出描述:
关键思路:
递归求左子节点深度与右子节点深度,最后相加即可
(2)代码块
class Solution {
public :
int result = 0 ;
int depth ( TreeNode* root)
{
if ( ! root)
return 0 ;
int L = depth ( root-> left) ;
int R = depth ( root-> right) ;
result = max ( result, L+ R) ;
return max ( L, R) + 1 ;
}
int diameterOfBinaryTree ( TreeNode* root)
{
depth ( root) ;
return result;
}
} ;
5、二叉树的直径
(1)题目描述以及输入输出
( 1 ) 题目描述:
给你一棵二叉树的根节点,返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
( 2 ) 输入输出描述:
关键思路:
递归求左子节点深度与右子节点深度,最后相加即可
(2)代码块
class Solution {
public :
int result = 0 ;
int depth ( TreeNode* root)
{
if ( ! root)
return 0 ;
int L = depth ( root-> left) ;
int R = depth ( root-> right) ;
result = max ( result, L+ R) ;
return max ( L, R) + 1 ;
}
int diameterOfBinaryTree ( TreeNode* root)
{
depth ( root) ;
return result;
}
} ;