LeetCode hot100---二叉树专题(C++语言)

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;}
};