二叉树 经典例题

94 中序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void inorder(TreeNode* root, vector<int>& res) {if (!root) return;inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);}vector<int> inorderTraversal(TreeNode* root) {vector<int> res;inorder(root, res);return res;}
};

104 二叉树的最大深度

左右树的最大深度 + 1

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {if (root == nullptr) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}
};

111 最小深度

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int minDepth(TreeNode* root) {if (root == nullptr) return 0;queue<TreeNode*> q;q.push(root);int depth = 1;while (!q.empty()) {int sz = q.size();for (int i = 0; i < sz; ++i) {auto cur = q.front();q.pop();if (cur->left == nullptr && cur->right == nullptr) return depth;if (cur->left != nullptr) q.push(cur->left);if (cur->right != nullptr) q.push(cur->right);}depth++;}return depth;}
};

226 翻转二叉树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {dfs(root);return root;}void dfs(TreeNode* root) {if (!root) return;TreeNode* tmp = root->left;root->left = root->right;root->right = tmp;dfs(root->left);dfs(root->right);}
};

101 对称二叉树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool check(TreeNode* p1, TreeNode* p2) {if (!p1 && !p2) {return true;}if (!p1 || !p2) {return false;}return (p1->val == p2->val) && (check(p1->left, p2->right)) && (check(p1->right, p2->left));}bool isSymmetric(TreeNode* root) {return check(root, root);}
};

222 完全二叉树节点数量（从左到右，从上到下依次排满）

复杂度 O(N)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int count = 0; // 统计节点数void inorder(TreeNode* root) {if(!root) return;inorder(root->left);count += 1;inorder(root->right);}int countNodes(TreeNode* root) {inorder(root);return count;}
};

k

2k 2k+1

h层，则最底层最右边元素是2^{h-1}最左边是2^{h}-1

二分

257 二叉树的所有路径

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/class Solution {
public:vector<string> binaryTreePaths(TreeNode* root) {// 创建一个存储路径的结果集vector<string> result;// 开始深度优先搜索dfs(root, "", result);return result;}void dfs(TreeNode* node, string path, vector<string>& result) {// 如果节点为空，返回if (node == nullptr) {return;}// *将当前节点值添加到路径中path += to_string(node->val);// 如果是叶子节点，将路径添加到结果集中if (node->left == nullptr && node->right == nullptr) {result.push_back(path);return;}// 如果不是叶子节点，继续深度优先搜索path += "->";dfs(node->left, path, result);dfs(node->right, path, result);}
};

404 左叶子之和

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int ans = 0;int sumOfLeftLeaves(TreeNode* root) {dfs(root);return ans;}void dfs(TreeNode* r) {if (r == nullptr) return;// 是左节点且是叶子节点if (r->left != nullptr && r->left->left == nullptr && r->left->right == nullptr) {ans += r->left->val;}dfs(r->left);dfs(r->right);}
};

100 相同的树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {return dfs(p, q);}bool dfs(TreeNode* r1, TreeNode* r2) {if (r1 == nullptr || r2 == nullptr) return r1 == r2;if (r1->val != r2->val) return false;return dfs(r1->left, r2->left) && dfs(r1->right, r2->right);}
};

513 树最左下角的值

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findBottomLeftValue(TreeNode* root) {// 更新每一层的第一个节点即可queue<TreeNode*> q;q.push(root);   int res = root->val;while (!q.empty()) {int cs = q.size();for (int i = 0; i < cs; ++i) {auto node = q.front();q.pop();if (i == 0) res = node->val;if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return res;}
};

543 二叉树的直径

class Solution {int ans;int depth(TreeNode* rt){if (rt == NULL) {return 0; // 访问到空节点了，返回0}int L = depth(rt->left); // 左儿子为根的子树的深度（即节点数）int R = depth(rt->right); // 右儿子为根的子树的深度ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ansreturn max(L, R) + 1; // 返回该节点为根的子树的深度}
public:int diameterOfBinaryTree(TreeNode* root) {ans = 1;depth(root);return ans - 1;}
};

102 二叉树的层序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (!root) {return res;}queue<TreeNode*> q;q.push(root);while(!q.empty()) {res.push_back(vector<int>());int currSize = q.size();for (int i = 1; i <= currSize; ++i) {auto node = q.front();q.pop();// 注意res.back().push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return res;}
};

110 平衡二叉树

任意节点左右子树高度差<=1

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int height(TreeNode* root) {if (root == NULL) {return 0;}else {return max(height(root->left), height(root->right)) + 1;}}bool isBalanced(TreeNode* root) {if (root == NULL) {return true;} else {return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);}}
};

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isBalanced(TreeNode* root) {dfs(root);return res;}bool res = true;int dfs(TreeNode* node) {if (node == nullptr) return 0;int l = dfs(node->left), r = dfs(node->right);if (abs(r - l) > 1) res = false;return std::max(l, r) + 1;}
};

230 二叉搜索树中第 k 小的元素

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int kthSmallest(TreeNode* root, int k) {stack<TreeNode*> stack;while (root != nullptr || stack.size() > 0) {// 先找小的while (root != nullptr) {stack.push(root);root = root->left;}root = stack.top();stack.pop();if (--k == 0) break;root = root->right;}return root->val;}
};

建树

后序最后一个节点是根节点-->确定左子树和右子树

106 中序 + 后序遍历构建二叉树

# Definition for a binary tree node.class Solution:def buildTree(self, inorder, postorder):# 使用哈希表存储中序遍历数组的值和对应的索引map = {val: idx for idx, val in enumerate(inorder)}# 开始递归构建树return self.dfs(0, len(inorder) - 1, 0, len(postorder) - 1, inorder, postorder, map)def dfs(self, in_left, in_right, post_left, post_right, inorder, postorder, map):# 如果中序遍历的左边界大于右边界，返回空节点if in_left > in_right:return None# 创建根节点，值为后序遍历的最后一个元素node = TreeNode(postorder[post_right])# 获取根节点在中序遍历中的索引in_index = map[postorder[post_right]]# 计算左子树节点个数left_cnt = in_index - in_left# 递归构建左右子树node.left = self.dfs(in_left, in_index - 1, post_left, post_left + left_cnt - 1, inorder, postorder, map)node.right = self.dfs(in_index + 1, in_right, post_left + left_cnt, post_right - 1, inorder, postorder, map)# 返回根节点return node