LeetCode热题100：二叉树

摘要

题目	知识点
94. 二叉树的中序遍历 - 力扣（LeetCode）	中序遍历
104. 二叉树的最大深度 - 力扣（LeetCode）	树的深度
226. 翻转二叉树 - 力扣（LeetCode）	树的翻转
101. 对称二叉树 - 力扣（LeetCode）	树的对称
543. 二叉树的直径 - 力扣（LeetCode）	树的直径
102. 二叉树的层序遍历 - 力扣（LeetCode）	层序遍历
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）	AVL树的构建
98. 验证二叉搜索树 - 力扣（LeetCode）
230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）
199. 二叉树的右视图 - 力扣（LeetCode）
114. 二叉树展开为链表 - 力扣（LeetCode）
105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
437. 路径总和 III - 力扣（LeetCode）
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
124. 二叉树中的最大路径和 - 力扣（LeetCode）

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

class Solution {
public:
	vector<int > in;
    
	void dfs(TreeNode *p){
		if(p == nullptr) return;
		dfs(p->left);
		in.push_back(p->val);
		dfs(p->right);
	}
    
	vector<int> inorderTraversal(TreeNode* p) {
		dfs(p);
		return in;
	}
};

二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

class Solution {
public:
	int maxDepth(TreeNode* p) {
		if(p == nullptr) return 0;
		return 1 + max(maxDepth(p->left), maxDepth(p->right));
	}
};

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

class Solution {
public:
	TreeNode* invertTree(TreeNode* p) {
		if(p == nullptr) return p;
		invertTree(p->left);
		invertTree(p->right);
		swap(p->left, p->right);
		return p;
	}
};

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

class Solution {
public:
	bool isSameNode(TreeNode *p1, TreeNode *p2){
		if(p1 == nullptr && p2 == nullptr) return true;
		if(p1 == nullptr || p2 == nullptr) return false;
		return p1->val == p2->val && isSameNode(p1->left, p2->right) && isSameNode(p1->right, p2->left);
	}
	
	bool isSymmetric(TreeNode* p) {
		return isSameNode(p->left, p->right);
	}
};

二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

class Solution {
public:
	int max_dep = 0;
    
    // 对每个节点，求出 经过该节点的最长路径
    // 这个最长路径 == 向左走的最大距离 + 向右走的最大距离；
    // 这个最长路径的全局最值 就是 树的直径
    
	int dfs(TreeNode *p){
		if(p == nullptr) return -1;
		int d1 = 1 + dfs(p->left); // 向左走的最大距离
		int d2 = 1 + dfs(p->right); // 向右走的最大距离
		max_dep = max(max_dep, d1 + d2);
		return max(d1, d2);
	}
	
	int diameterOfBinaryTree(TreeNode* p) {
		dfs(p);
		return max_dep;
	}
};

二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

class Solution {
public:
	vector<vector<int>> levelOrder(TreeNode* p) {
		if(p == nullptr) return {};
		vector<vector<int> > lev;
		queue<TreeNode* > q;
		q.push(p);
		while(!q.empty()){
			vector<int > v;
			int cur = q.size();
			while(cur--){
				TreeNode *f = q.front(); q.pop();
				v.push_back(f->val);
				if(f->left) q.push(f->left);
				if(f->right) q.push(f->right);
			}
			lev.push_back(v);
		}
		return lev;
	}
};

将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

class Solution {
public:
	TreeNode* build(vector<int>& nums, int l, int r){
		if(l > r) return nullptr;
		int mid = (l+r)/2;
		TreeNode *root = new TreeNode(nums[mid]);
		root->left = build(nums, l, mid-1);
		root->right = build(nums, mid+1, r);
		return root;
	}
	
	TreeNode* sortedArrayToBST(vector<int>& nums) {
		return build(nums, 0, nums.size()-1);
	}
};