网站导航
> 文章列表 > 二叉树总结

二叉树总结

网友: 文章列表 2024-03-21 18:41:16

二叉树总结

LeetCode题目

  • 深度优先搜索（前、中、后序遍历）
    • 144.二叉树的前序遍历
    • 94.二叉树的中序遍历
    • 145.二叉树的后序遍历
    • 257.二叉树的所有路径
    • 112.路径总和
    • 113.路径总和 II
  • 广度优先搜索（层序遍历）
    • 102.二叉树的层序遍历
    • 107.二叉树的层序遍历 II
    • 199.二叉树的右视图
    • 637.二叉树的层平均值
    • 429.N 叉树的层序遍历
    • 515.在每个树行中找最大值
    • 116.填充每个节点的下一个右侧节点指针
    • 117.填充每个节点的下一个右侧节点指针 II
    • 104.二叉树的最大深度
    • 111.二叉树的最小深度
    • 513.找树左下角的值
  • 深搜、广搜皆可
    • 404.左叶子之和
    • 226.翻转二叉树
    • 100.相同的树
    • 101.对称二叉树
    • 572.另一棵树的子树
    • 222.完全二叉树的节点个数
    • 110.平衡二叉树
  • 构造二叉树
    • 105.从前序与中序遍历序列构造二叉树
    • 106.从中序与后序遍历序列构造二叉树
    • 654.最大二叉树
    • 617.合并二叉树
    • 108.将有序数组转换为二叉搜索树
  • 二叉搜索树
    • 700.二叉搜索树中的搜索
    • 98.验证二叉搜索树
    • 530.二叉搜索树的最小绝对差
    • 501.二叉搜索树中的众数
    • 538.把二叉搜索树转换为累加树
    • 701.二叉搜索树中的插入操作
    • 450.删除二叉搜索树中的节点
    • 669.修剪二叉搜索树
    • 235.二叉搜索树的最近公共祖先
    • 236.二叉树的最近公共祖先

简介

  • 本文是二叉树的大总结，二叉树和链表都是特殊的数据结构，题目问到这两种结构，基本套路就这么多
  • 链表可参考链表LeetCode总结
  • 本文尽可能采用迭代法，便于理解
  • 二叉树节点结构体要会背
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int _val = -1, TreeNode* _left = nullptr, TreeNode* _right = nullptr): val(_val), left(_left), right(_right){}
};
  • 按照解法来分类讲解

深度优先搜索（前、中、后序遍历）

  • 所谓前、中、后序遍历，指的是当前二叉树的根节点的遍历位置
    • 前序遍历的顺序：[中,前,后]
    • 中序遍历的顺序：[前,中,后]
    • 后序遍历的顺序：[前,后,中]
  • 迭代法遍历模板
    • 前序遍历
    stack<TreeNode*> sta;
sta.emplace(root);
while (!sta.empty()) {auto cur = sta.top();sta.pop();...// 注意要先emplace右节点，因为stack是先进后出的if (cur->right)sta.emplace(cur->right);if (cur->left)sta.emplace(cur->left);
}
    • 中序遍历
    stack<TreeNode*> sta;
auto cur = root;
while (cur || !sta.empty()) {if (cur) {sta.emplace(cur);cur = cur->left;} else {cur = sta.top();sta.pop();...cur = cur->right;}
}
    • 后序遍历
    stack<TreeNode*> sta;
auto cur = root, pre = root;
pre = nullptr;
while (cur || !sta.empty()) {if (cur) {sta.emplace(cur);cur = cur->left;} else {cur = sta.top();// 只有当cur节点没有right子树，或者已经遍历了right子树// 才能遍历cur节点，否则需要进入right子树if (!cur->right || pre == cur->right) {sta.pop();...// 遍历结束，记录当前节点为pre，置cur为nullptrpre = cur;cur = nullptr;} elsecur = cur->right;}
}
  • 深度优先搜索适用于需要保留二叉树拓扑结构的题目，比如从根节点到叶节点的路径
  • 257.二叉树的所有路径
// 本题用前序遍历更直接
class Solution {
public:vector<string> binaryTreePaths(TreeNode* root){if (!root)return {};vector<string> ans;stack<TreeNode*> sta;sta.emplace(root);// 记录路径，类似sta那样运作stack<string> paths;paths.emplace(to_string(root->val) + "->");while (!sta.empty()) {auto cur = sta.top();sta.pop();auto path = paths.top();paths.pop();// 到了叶节点，则emplace_back到ans中if (!cur->left && !cur->right) {path.resize(path.size() - 2);ans.emplace_back(path);}if (cur->right) {sta.emplace(cur->right);paths.emplace(path + to_string(cur->right->val) + "->");}if (cur->left) {sta.emplace(cur->left);paths.emplace(path + to_string(cur->left->val) + "->");}}return ans;}
};
  • 113.路径总和 II
class Solution {
public:vector<vector<int>> pathSum(TreeNode* root, int targetSum){if (!root)return {};vector<vector<int>> ans;stack<TreeNode*> sta;sta.emplace(root);// 用pair记录path和对应的sumstack<pair<vector<int>, int64_t>> sta_pair;sta_pair.emplace(pair<vector<int>, int64_t> {vector<int> { root->val }, root->val });while (!sta.empty()) {auto cur = sta.top();sta.pop();auto pair = sta_pair.top();sta_pair.pop();if (!cur->left && !cur->right) {if (pair.second == targetSum)ans.emplace_back(pair.first);}if (cur->left) {sta.emplace(cur->left);pair.first.emplace_back(cur->left->val);pair.second += cur->left->val;sta_pair.emplace(pair);pair.first.pop_back();pair.second -= cur->left->val;}if (cur->right) {sta.emplace(cur->right);pair.first.emplace_back(cur->right->val);pair.second += cur->right->val;sta_pair.emplace(pair);}}return ans;}
};

广度优先搜索（层序遍历）

  • 所谓层序遍历，指的是按照二叉树的树层的顺序进行遍历，直至某一树层全为叶节点，则结束
  • 迭代法遍历模板
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root){if (!root)return {};// 记录全部树层vector<vector<int>> ans;// 记录每一树层vector<int> ans2;queue<TreeNode*> que;que.emplace(root);while (!que.empty()) {auto size = que.size();// 清空上一个树层的记录ans2.resize(0);while (size--) {auto cur = que.front();que.pop();// 记录当前树层ans2.emplace_back(cur->val);if (cur->left)que.emplace(cur->left);if (cur->right)que.emplace(cur->right);}// 当前树层记录完成，emplace_back到ans中ans.emplace_back(ans2);}return ans;}
};
  • 只要涉及树层级别的遍历，就可以用层序遍历
  • 429.N 叉树的层序遍历
class Node {
public:int val;vector<Node*> children;Node() { }Node(int _val) { val = _val; }Node(int _val, vector<Node*> _children){val = _val;children = _children;}
};class Solution {
public:vector<vector<int>> levelOrder(Node* root){if (!root)return {};vector<vector<int>> ans;vector<int> ans2;queue<Node*> que;que.emplace(root);while (!que.empty()) {auto size = que.size();ans2.resize(0);while (size--) {auto cur = que.front();que.pop();ans2.emplace_back(cur->val);for (auto& node : cur->children) {if (node)que.emplace(node);}}ans.emplace_back(ans2);}return ans;}
};

深搜、广搜皆可

  • 对于只需要遍历每个树节点的题目，则深搜广搜皆可

  • 226.翻转二叉树

class Solution {
public:TreeNode* invertTree(TreeNode* root){if (!root)return {};queue<TreeNode*> que;que.emplace(root);while (!que.empty()) {auto size = que.size();while (size--) {auto cur = que.front();que.pop();// 关键的处理步骤swap(cur->left, cur->right);if (cur->left)que.emplace(cur->left);if (cur->right)que.emplace(cur->right);}}return root;}
};
  • 需要同时处理两棵树的题目
  • 100.相同的树
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q){queue<TreeNode*> que;que.emplace(p);que.emplace(q);while (!que.empty()) {auto node = que.front();que.pop();auto node2 = que.front();que.pop();if (!node && !node2)continue;if ((!node && node2) || (node && !node2))return false;if (node->val != node2->val)return false;// emplace的顺序很关键，要求相同位置的节点，值相同que.emplace(node->left);que.emplace(node2->left);que.emplace(node->right);que.emplace(node2->right);}return true;}
};
  • 101.对称二叉树
class Solution {
public:bool isSymmetric(TreeNode* root){if (!root)return true;queue<TreeNode*> que;que.emplace(root->left);que.emplace(root->right);while (!que.empty()) {auto size = que.size();while (size) {auto node = que.front();que.pop();auto node2 = que.front();que.pop();if ((!node && node2) || (node && !node2))return false;if (node && node2) {if (node->val != node2->val)return false;// 关键在于emplace的顺序// 要求对称位置的节点，值相同que.emplace(node->left);que.emplace(node2->right);que.emplace(node->right);que.emplace(node2->left);}size -= 2;}}return true;}
};
  • 572.另一棵树的子树
// 对root中的每一个子树，都要进行“是否是相同的树”判断
class Solution {
private:bool isSameTree(TreeNode* root, TreeNode* root2){queue<TreeNode*> que;que.emplace(root);que.emplace(root2);while (!que.empty()) {auto node = que.front();que.pop();auto node2 = que.front();que.pop();if (!node && !node2)continue;if ((!node && node2) || (node && !node2))return false;if (node->val != node2->val)return false;que.emplace(node->left);que.emplace(node2->left);que.emplace(node->right);que.emplace(node2->right);}return true;}public:// 任意一种遍历方法皆可bool isSubtree(TreeNode* root, TreeNode* subRoot){if (!root && !subRoot)return true;if ((!root && subRoot) || (root && !subRoot))return false;stack<TreeNode*> sta;auto cur = root, pre = root;pre = nullptr;while (cur || !sta.empty()) {if (cur) {sta.emplace(cur);cur = cur->left;} else {cur = sta.top();if (!cur->right || pre == cur->right) {sta.pop();pre = cur;// 对每个节点所构成的子树检查是否相同if (isSameTree(cur, subRoot))return true;cur = nullptr;} elsecur = cur->right;}}return false;}
};
  • 617.合并二叉树
class Solution {
private:// 关键逻辑：如果其中一个节点为nullptr，则由另一个节点代替TreeNode* helper(TreeNode* node, TreeNode* node2){if (!node)return node2;if (!node2)return node;return node;}public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2){if (!root1)return root2;if (!root2)return root1;stack<TreeNode*> sta;sta.emplace(root1);sta.emplace(root2);while (!sta.empty()) {auto cur2 = sta.top();sta.pop();auto cur = sta.top();sta.pop();// 处理非nullptr的节点cur->val += cur2->val;if (cur->left && cur2->left) {sta.emplace(cur->left);sta.emplace(cur2->left);}if (cur->right && cur2->right) {sta.emplace(cur->right);sta.emplace(cur2->right);}// 处理nullptr的节点cur->left = helper(cur->left, cur2->left);cur->right = helper(cur->right, cur2->right);}return root1;}
};
  • 需要利用到二叉树的性质的题目
  • 222.完全二叉树的节点个数
  • 110.平衡二叉树
 // 本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。class Solution {
private:int height(TreeNode* root){if (!root)return 0;auto ans = 0;queue<TreeNode*> que;que.emplace(root);while (!que.empty()) {++ans;auto size = que.size();while (size--) {auto cur = que.front();que.pop();if (cur->left)que.emplace(cur->left);if (cur->right)que.emplace(cur->right);}}return ans;}public:bool isBalanced(TreeNode* root){if (!root)return true;queue<TreeNode*> que;que.emplace(root);while (!que.empty()) {auto size = que.size();while (size--) {auto cur = que.front();que.pop();// 对每个节点的左右子树检查高度差auto left_height = height(root->left);auto right_height = height(root->right);if (abs(left_height - right_height) > 1)return false;if (cur->left)que.emplace(cur->left);if (cur->right)que.emplace(cur->right);}}return true;}
};

构造二叉树

  • 构造二叉树通常用递归比较好理解
  • 105.从前序与中序遍历序列构造二叉树
// 前序遍历的第一个值是根节点
// 并且题目说了无重复元素，因此利用根节点的值，分割中序遍历
class Solution {
private:// 利用哈希表，构建中序遍历的值和下标索引，快速分割中序遍历unordered_map<int, int> hash_map;// 传入当前节点的前序遍历和中序遍历，在数组中的范围[begin, end)，从而避免拷贝// 每次递归调用，都返回一个子树的根节点TreeNode* helper(vector<int>& in, int in_begin, int in_end,vector<int>& pre, int pre_begin, int pre_end){auto size = pre_begin - pre_end;// 当数组长度为0，说明当前节点为空节点if (0 == size)return nullptr;auto cur_val = pre[pre_begin];auto cur = new TreeNode(cur_val);// 当数组长度为1，说明当前节点为叶节点if (1 == size)return cur;auto cur_index = hash_map[cur_val];// 分割出左右子树的前、中序遍历cur->left = helper(in, in_begin, cur_index, pre, pre_begin + 1,pre_begin + 1 + cur_index - in_begin);cur->right = helper(in, cur_index + 1, in_end, pre,pre_begin + 1 + cur_index - in_begin, pre_end);return cur;}public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){auto size = inorder.size();for (auto i = 0; i < size; ++i)hash_map[inorder[i]] = i;return helper(inorder, 0, size, preorder, 0, size);}
};
  • 654.最大二叉树
// 和上题类似
class Solution {
private:TreeNode* helper(vector<int>& nums, int begin, int end){auto size = end - begin;if (0 == size)return nullptr;auto max_index = begin;for (auto i = begin + 1; i < end; ++i) {if (nums[i] > nums[max_index])max_index = i;}auto cur = new TreeNode(nums[max_index]);if (1 == size)return cur;cur->left = helper(nums, begin, max_index);cur->right = helper(nums, max_index + 1, end);return cur;}public:TreeNode* constructMaximumBinaryTree(vector<int>& nums){auto size = nums.size();return helper(nums, 0, size);}
};
  • 108.将有序数组转换为二叉搜索树
class Solution {
private:TreeNode* helper(vector<int>& nums, int begin, int end){// 由于数组已升序排序，所以可采用二分搜索找到当前的根节点（即中位数）auto size = end - begin;if (0 == size)return nullptr;auto mid = ((end - begin) >> 1) + begin;auto cur = new TreeNode(nums[mid]);if (1 == size)return cur;cur->left = helper(nums, begin, mid);cur->right = helper(nums, mid + 1, end);return cur;}public:TreeNode* sortedArrayToBST(vector<int>& nums){auto size = nums.size();return helper(nums, 0, size);}
};

二叉搜索树

  • 二叉搜索树是有序的，若一个二叉搜索树的：
    • 左子树不为空，则左子树上的所有节点的值，都小于根节点
    • 右子树不为空，则右子树上的所有节点的值，都大于根节点
  • 二叉搜索树的充要条件：中序遍历是有序的
  • 可利用前序遍历，查找符合条件的值，复杂度O(h)O(h)O(h)，h是二叉搜索树的高度。对于高度平衡的二叉搜索树而言，前序遍历复杂度O(log⁡n)O(\\log n)O(logn)
  • 98.验证二叉搜索树
// 利用充要条件：中序遍历是有序的
class Solution {
public:bool isValidBST(TreeNode* root){if (!root)return true;stack<TreeNode*> sta;vector<int> ans;auto cur = root;while (cur || !sta.empty()) {if (cur) {sta.emplace(cur);cur = cur->left;} else {cur = sta.top();sta.pop();ans.emplace_back(cur->val);cur = cur->right;}}for (auto i = 1; i < ans.size(); ++i) {if (ans[i] <= ans[i - 1])return false;}return true;}
};
  • 501.二叉搜索树中的众数
// 由于中序遍历有序，所以可以不用哈希表
// 而是在遍历过程中进行计数，而不会遗漏
class Solution {
public:vector<int> findMode(TreeNode* root){if (!root)return {};vector<int> ans;auto pre = root;pre = nullptr;auto count = 0, max_count = 0;stack<TreeNode*> sta;auto cur = root;while (cur || !sta.empty()) {if (cur) {sta.emplace(cur);cur = cur->left;} else {cur = sta.top();sta.pop();// 当cur为root时，只需要count=1，然后无其他操作// 当cur不为root，如果cur值和pre值相同，则++count// 若不同，则比较count和max_count，从而决定清空ans，还是追加ansif (pre != nullptr) {if (cur->val == pre->val)++count;else {if (count > max_count) {ans.clear();ans.emplace_back(pre->val);max_count = count;} else if (count == max_count)ans.emplace_back(pre->val);count = 1;}} elsecount = 1;pre = cur;cur = cur->right;}}// 由于是当cur值和pre值不同时，才比较count和max_count// 所以对最后一个值需要单独处理if (count > max_count) {ans.clear();ans.emplace_back(pre->val);} else if (count == max_count)ans.emplace_back(pre->val);return ans;}
};
  • 修改二叉搜索树
  • 701.二叉搜索树中的插入操作
// 前序遍历，查找插入的位置
class Solution {
private:// 判断：若target小于cur，则返回-1，target应该在左子树的位置// 若target大于cur，则返回1，target应该在右子树的位置int compare(int cur, int target){if (cur > target)return -1;if (cur < target)return 1;return 0;}public:TreeNode* insertIntoBST(TreeNode* root, int val){if (!root)return new TreeNode(val);stack<TreeNode*> sta;sta.emplace(root);while (!sta.empty()) {auto cur = sta.top();sta.pop();auto result = compare(cur->val, val);// 对cur的左右子树的四种情况分类讨论即可if (!cur->left && !cur->right) {if (-1 == result)cur->left = new TreeNode(val);elsecur->right = new TreeNode(val);break;} else if (!cur->left && cur->right) {if (-1 == result) {cur->left = new TreeNode(val);break;} elsesta.emplace(cur->right);} else if (cur->left && !cur->right) {if (1 == result) {cur->right = new TreeNode(val);break;} elsesta.emplace(cur->left);} else if (cur->left && cur->right) {if (-1 == result)sta.emplace(cur->left);elsesta.emplace(cur->right);}}return root;}
};
  • 450.删除二叉搜索树中的节点
class Solution {
private:int compare(int cur, int target){if (cur > target)return -1;if (cur < target)return 1;return 0;}// 关键在此：当需要删除cur，应该返回哪个节点// 如果cur没有右子树，则返回左节点// 如果cur有右子树，则遍历出右子树的第一个左叶节点// 将cur的左子树，接到该左叶节点的左节点上// 最后返回cur的右节点TreeNode* helper(TreeNode* cur){auto right_left = cur->right;if (!right_left)return cur->left;while (right_left->left)right_left = right_left->left;right_left->left = cur->left;return cur->right;}public:TreeNode* deleteNode(TreeNode* root, int val){if (!root)return root;auto result = compare(root->val, val);if (0 == result)return helper(root);stack<TreeNode*> sta;sta.emplace(root);while (!sta.empty()) {auto cur = sta.top();sta.pop();if (cur->left && 0 == compare(cur->left->val, val)) {cur->left = helper(cur->left);break;}if (cur->right && 0 == compare(cur->right->val, val)) {cur->right = helper(cur->right);break;}result = compare(cur->val, val);if (-1 == result) {if (cur->left)sta.emplace(cur->left);} else {if (cur->right)sta.emplace(cur->right);}}return root;}
};
  • 669.修剪二叉搜索树
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high){if (!root || low > high)return root;// 本题逻辑：先定位root，使root->val满足[low, high]// 然后修剪左子树和右子树，使其满足条件auto cur = root;while (cur) {if (cur->val < low)cur = cur->right;else if (cur->val > high)cur = cur->left;elsebreak;}// 修剪左子树的逻辑：遍历检查左节点是否小于low，不需要检查是否大于high// 若小于low，则赋值左节点，为左节点的右节点// 直至左节点大于low，则进入左节点，重复上述过程，直至左节点为nullptrauto cur2 = cur;while (cur2) {while (cur2->left && cur2->left->val < low)cur2->left = cur2->left->right;cur2 = cur2->left;}// 修剪右子树的逻辑：遍历检查右节点是否大于high，不需要检查是否小于low// 若大于high，则赋值右节点，为右节点的左节点// 直至左节点小于high，则进入右节点，重复上述过程，直至右节点为nullptrcur2 = cur;while (cur2) {while (cur2->right && cur2->right->val > high)cur2->right = cur2->right->left;cur2 = cur2->right;}return cur;}
};
  • 最近公共祖先问题
  • 235.二叉搜索树的最近公共祖先
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){if (!root)return NULL;stack<TreeNode*> sta;sta.emplace(root);while (!sta.empty()) {auto cur = sta.top();sta.pop();// 明确逻辑：按照前序遍历// 1.如果当前值为p或q，则当前值为最近公共祖先// 2.如果p和q分别在左右子树，则当前值为最近公共祖先// 3.如果p和q都在某一子树，则前往该子树继续寻找if (cur->val == p->val || cur->val == q->val)return cur;if (p->val > cur->val && q->val < cur->val)return cur;if (p->val < cur->val && q->val > cur->val)return cur;if (cur->val > p->val && cur->val > q->val)sta.emplace(cur->left);if (cur->val < p->val && cur->val < q->val)sta.emplace(cur->right);}return NULL;}
};
  • 236.二叉树的最近公共祖先
// 本题逻辑同上题
// 采用递归法，因为迭代法无法逐层往上传结果
// 关于迭代法，可参考lowestCommonAncestor2
class Solution {
private:vector<TreeNode*> sta;TreeNode* postOrderSearch(TreeNode* root, TreeNode* p, TreeNode* q){if (!root)return NULL;sta.resize(0);auto cur = root, pre = root;pre = NULL;while (cur || !sta.empty()) {if (cur) {sta.emplace_back(cur);cur = cur->left;} else {cur = sta.back();if (!cur->right || pre == cur->right) {sta.pop_back();pre = cur;if (cur->val == p->val || cur->val == q->val)return cur;cur = NULL;} elsecur = cur->right;}}return NULL;}public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){if (!root)return root;if (p->val == root->val || q->val == root->val)return root;auto left_result = lowestCommonAncestor(root->left, p, q);auto right_result = lowestCommonAncestor(root->right, p, q);if (left_result && right_result)return root;if (!left_result && right_result)return right_result;if (left_result && !right_result)return left_result;return NULL;}TreeNode* lowestCommonAncestor2(TreeNode* root, TreeNode* p, TreeNode* q){if (!root)return root;stack<TreeNode*> sta;sta.emplace(root);while (!sta.empty()) {auto cur = sta.top();sta.pop();if (p->val == cur->val || q->val == cur->val)return cur;auto left_result = postOrderSearch(cur->left, p, q);auto right_result = postOrderSearch(cur->right, p, q);if (left_result && right_result)return cur;if (!left_result && right_result)sta.emplace(cur->right);if (left_result && !right_result)sta.emplace(cur->left);}return NULL;}
};

安陆市

网络标签：

相关问题