网站导航
> 文档中心 > LeetCode - 树专题

LeetCode - 树专题

文档中心 2022-05-25 17:24:03 40

文章目录

  • 一、树
  • 二、刷题
      • 二叉树的前/中/后序题目汇总
      • 二叉树的层序遍历题目汇总
      • 二叉搜索树题目汇总

一、树

结构：树是链表结构的扩展，每个节点都有 左右指针 ，用于指向下一个节点。
遍历：链表只有一个分叉，遍历的时候直接遍历即可；树分两个叉，遍历的时候用 递归 的方式。
   树为什么适合用递归写法？
   因为树天然具有递归的性质，子树的性质和整个树的性质一致；使用递归可以轻松地将整个树问题转换成子树问题。当层层递归到最小子树时，这个最小子树的解（也称为递归出口）往往很容易得到，然后再一步步回溯就能得到原问题的解。

树递归的思路（最简公式）：① 写出子问题的推导（归纳成一个子问题）; ② 写出终止条件。

树的前/中/后序遍历：

(1) 前序遍历（自顶向下）：在每个递归层级上首先访问节点来计算一些值；并在递归调用函数时将这些值通过参数传递到子树中。

(2) 后序遍历（自底向上）：首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案，依赖左右子树的返回值。

(3) 中序遍历

什么时候用前/中/后序遍历呢？

(1) 如果能使用参数和节点本身的值来决定应该传递给它的子节点的参数，就用前序遍历。

(2) 对于树中的任意一个节点，如果知道它子节点的答案，就能计算出当前节点的答案，就用后序遍历。

(3) 如果遇到二叉搜索树，就用中序遍历。

二、刷题

二叉树的前/中/后序题目汇总

LeetCode 104 二叉树的最大深度 原题链接

  • (1) 归纳成一个子问题（子问题的推导）：一棵树的最大深度等于左子树和右子树的深度最大的那个 +1 1 1；
  • (2) 终止条件；
class Solution {public:    int maxDepth(TreeNode* root) { if (!root) return 0; // 终止条件，这样就可以依次对外返回，得到整棵树的深度 int maxleft = maxDepth(root->left); int maxright = maxDepth(root->right); return max(maxleft, maxright) + 1;    }};

LeetCode 226 翻转二叉树 原题链接

  • (1) 翻转左右节点，swap(root->left, root->right)，该节点的左右节点翻转过来了；
  • (2) 递归反转左右子树 swap(invertTree(root->left), invertTree(root->right))；
class Solution {public:    TreeNode* invertTree(TreeNode* root) { if (!root) return NULL; swap(root->left, root->right); invertTree(root->left); invertTree(root->right); return root;    }};

LeetCode 144 二叉树的前序遍历 原题链接

  1. 递归写法
    (1) 先处理当前节点；
    (2) 递归处理左子树和右子树；

  2. 迭代写法：
    (1) 需要一个栈；
    (2) 每次遍历栈时：
      ① 每次都弹出来一个元素；
      ② 进行处理；
      ③ 将其右左节点推进栈中（这样就会不停的遍历栈）；

// 递归写法class Solution {public:    vector<int> res;    vector<int> preorderTraversal(TreeNode* root) { dfs(root); return res;    }    void dfs(TreeNode* root)    { if (!root) return; res.push_back(root->val); dfs(root->left); dfs(root->right);    }};// 迭代写法// 输入没有空，// 输入：root = []：表示数组长度为0，输出：[]：表示返回一个空数组class Solution {public:    vector<int> res;    stack<TreeNode*> stk;    vector<int> preorderTraversal(TreeNode* root) { if (!root) return res; // 这个可以省略，因为输入没有空节点 stk.push(root); while (stk.size()) {     auto t = stk.top();     stk.pop();     res.push_back(t->val);     if (t->right) stk.push(t->right); // 注意先放右节点，再放左节点     if (t->left) stk.push(t->left); } return res;    }};

LeetCode 100 相同的树 原题链接

  • 判断两个树当前节点的值是否相等，如果相等，两棵树的左子树和右子树是否相等。
class Solution {public:    bool isSameTree(TreeNode* p, TreeNode* q) { // 相同：1、在结构上相同   2、节点值相同  // 下面3个if是不需要进行递归的逻辑 // 1、提前预判：如果两个都是NULL，就不用参与树型判断的逻辑。2、在递归的时候如果递归到两个子树都是NULL也认为相等 if (p == NULL && q == NULL) return true;  // 如果两个不全是NULL，两个都是NULL情况上面已经处理过，如果有一个是NULL，另外一个不是NULL。 if (p == NULL || q == NULL) return false; // 先判断不相等，为什么？因为它俩值相等的情况下需要进行递归，两个节点相等并不代表两个树相等，还需要深入到底层看其子元素是否相等 if (p->val != q->val) return false; // 两个节点值一样，需要递归的判断 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);    }};

LeetCode 101 对称二叉树 原题链接

  • (1) 比较的不是左右节点，而是左右子树，所以在递归遍历的过程中，也需要同时遍历这两棵树；
  • (2) 考虑的时候一般先考虑的是一个局部信息(最小的子树，此题中最小的子树是 3 3 3 个节点的子树)；
  • (3) 求的时候我们只需要考虑如何维护这些信息即可：要求当前树是否为对称二叉树，考虑它的左右子树是否是对称二叉树，如果左右子树都是对称二叉树，那么当前树就是对称二叉树。假设以 u为根节点的树是否为对称二叉树记为 f(u)，要考虑的就是 f(u)与 f(a)和 f(b)的关系，一般只需要考虑这样一个局部信息即可，只要捋清楚 f(u)与 f(a)和 f(b)之间的关系，则可以递归地求出来每一个 f(u)， f(root)就是答案；
class Solution {public:    bool isSymmetric(TreeNode* root) { return dfs(root->left, root->right);    }    bool dfs(TreeNode* p, TreeNode* q)    { if (p == NULL && q == NULL) return true; if (p == NULL || q == NULL) return false; if (p->val != q->val) return false; // 判断对称：值相等并且子元素满足关系 return dfs(p->left, q->right) && dfs(p->right, q->left);    }};

LeetCode 111 二叉树的最小深度 原题链接

  • 注意需要单独判断如果没有左子树和右子树的情况。
class Solution {public:    int minDepth(TreeNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; if (root->left == NULL) return minDepth(root->right) + 1; if (root->right == NULL) return minDepth(root->left) + 1; return min(minDepth(root->left), minDepth(root->right)) + 1;    }};

LeetCode 617 合并二叉树 原题链接

class Solution {public:    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if (!root1 && !root2) return NULL; if (!root1) return root2; if (!root2) return root1; root1->val += root2->val; root1->left = mergeTrees(root1->left, root2->left); root1->right  = mergeTrees(root1->right, root2->right); return root1;    }};

LeetCode 236 二叉树的最近公共祖先 原题链接

  • (1) 采用后序遍历不停地向上查找，直到找到一个交叉的地方；
  • (2) 判断当前节点，当前的节点不停往下找（遍历每一个节点），如果两边都找到了，那么一边一个 p和 q（p和 q没有嵌套关系），或者同时在左边或右边（p 和 q有嵌套关系）；
class Solution {public:    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root) return NULL; if (root == p || root == q) return root; // 如果p或q有一个是根节点(p和q有嵌套关系)就不用查找了，直接预判了 auto left = lowestCommonAncestor(root->left, p, q); // 在左子树找p和q， auto right = lowestCommonAncestor(root->right, p, q); // 在右子树找p和q， if (left && right) return root; // 因为题目规定定义两个节点都在，如果左右子树都找到了，那一定是一边一个，那最近公共祖先就是当前的root return left ? left : right; // 如果p和q都在左边或者都在右边（哟嵌套关系）    }};

LeetCode 572 另一棵树的子树 原题链接

  • 不停地比较 root中的某一个子树和 subRoot是否相同。
// 平级对比和递归嵌套的层级去对比class Solution {public:    bool isSubtree(TreeNode* root, TreeNode* subRoot) { if (!root) return false; if (root->val == subRoot->val) // 有子树的可能性继续递归比较 {     if (isSameTree(root, subRoot)) return true; // 这块不能直接return isSameTree } // 如果不是的话，需要判断它的子树 return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);    }    bool isSameTree(TreeNode* p, TreeNode* q)    { if (!p && !q) return true; if (!p || !q) return false; if (p->val != q->val) return false; return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);    }};

LeetCode 257 二叉树的所有路径 原题链接

  • 采用前序遍历，在进入节点的时候进行操作。
class Solution {public:    vector<string> res;    vector<int> path;    vector<string> binaryTreePaths(TreeNode* root) { if (root) dfs(root); return res;    }    void dfs(TreeNode* root)    { path.push_back(root->val); if (!root->left && !root->right) {     string line = to_string(path[0]);     for (int i = 1; i < path.size(); i ++)     {  line += "->" + to_string(path[i]);     }     res.push_back(line); } if (root->left) {     dfs(root->left);     // path.pop_back(); } if (root->right) {     dfs(root->right);     // path.pop_back(); } path.pop_back();    }};

LeetCode 112 路径总和 原题链接

  • 自顶向下，前序遍历+参数扩展；在向下递归的时候同时更新参数，当达到叶子节点是判断是否满足条件；
  • 后序遍历：即在递归函数返回时对问题进行求解，使用子树的返回值来计算当前节点的值；
  • 搜索这个二叉树的不同路径，如果找到一条符合条件的路径就返回 true，如果所有路径都不复合要求就返回 false；
class Solution {public:    bool hasPathSum(TreeNode* root, int targetSum) { if (!root) return false; targetSum -= root->val; if (!root->left && !root->right)     return !targetSum; return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);    }};

LeetCode 113 路径总和II 原题链接

  • 与上一题的区别是要找到所有符合条件的路径，上一题只需要判断是否存在一条符合条件的路径。
class Solution {public:    vector<vector<int>> res;    vector<int> path;    vector<vector<int>> pathSum(TreeNode* root, int targetSum) { if (root) dfs(root, targetSum); return res;    }    void dfs(TreeNode* root, int targetSum)    { targetSum -= root->val; path.push_back(root->val); if (!root->left && !root->right && !targetSum)     res.push_back(path); // 如果到达叶子节点的话下面这两个条件不会执行 if (root->left) dfs(root->left, targetSum); if (root->right) dfs(root->right, targetSum); path.pop_back();    }};

LeetCode 543 二叉树的直径 原题链接

  • 自底向上，用后序遍历，先遍历左右再处理自己。
class Solution {public:    int len = 0;    int diameterOfBinaryTree(TreeNode* root) { dfs(root); return len;    }    int dfs(TreeNode* root)    { if (!root) return 0; int left = dfs(root->left); int right = dfs(root->right); len = max(len, left + right); return max(left, right) + 1;    }};

LeetCode 124 二叉树中的最大路径和 原题链接

  • 首先明确路径的定义：路径被定义成一条从树中任意节点出发并达到任意节点的序列，该路径至少包含一个节点，且不一定经过根节点。可以用同种逻辑处理问题及其子问题的情况，使用递归思想。

  • 先思考只有三个点的最简单的情况(子树)
    如果上面的这个子树是整个树的一部分：
    ①：整个树的最大路径和就在这个子树当中，不再经过这个子树外的其它节点，最终结果 a + b + c；
    ②：最大路径和包含节点a，并且通过a扩展到子树外的其它节点，最终结果 max(b, c) + a + parent(a)，parent(a)表示节点 a 往外延伸的剩余部分的路径和；
    ③：不包含子树 a；
    抽象：将节点 b，c 抽象成任意一个子树的左右子树；

  • 设定一个全局变量存储最大路径和，不断递归搜索每个子树更新该变量
    1、搜索最左边的最小子树，不断回溯到更大一点的子树，直到 root节点的整个子树被搜索完；
    2、然后对 root节点的右子树做同样操作；
    3、判断包含 root节点的情况；

class Solution {public:    int res;    int maxPathSum(TreeNode* root) { res = INT_MIN; dfs(root); return res;    }    int dfs(TreeNode* root)    { if (!root) return 0; // 如果下面是负数就不用取了，故和0取max int left = max(0, dfs(root->left)), right = max(0, dfs(root->right)); res = max(res, root->val + left + right); return root->val + max(left, right);    }};
  • 将所有路径都枚举出来，然后将最值求出来。在树中枚举路径的常用方式，枚举这个路径的最高点，枚举某个点的时候考虑以这个点为最高点的所有路径里边和最大的一条路径和
    对于某个点的路径有两部分，一部分是往左子树走，另一部分是往右子树走，左子树和右子树是没有任何交集（任何公共点和公共边）的，左右子树是完全独立的，以根节点分隔的左右两侧是完全独立的，让整个路径最大， 让左右两边都取最大值。

LeetCode 110 平衡二叉树 原题链接

  • 当前节点的求值依赖于左右节点，故采用后序遍历；
  • 注意全局变量的使用，每次递归看是否修改了全局变量；
class Solution {public:    bool ans;    bool isBalanced(TreeNode* root) { ans = true; dfs(root); return ans;    }    int dfs(TreeNode* root)    { if (!root) return 0; int lh = dfs(root->left); int rh = dfs(root->right); if (abs(lh - rh) > 1) ans = false; return max(lh, rh) + 1;    }};

二叉树的层序遍历题目汇总

  • 用队列模拟层序遍历的逻辑（队列先进先出，符合一层一层遍历的逻辑），用栈来模拟递归的逻辑（栈先进后出符合递归的逻辑）。

  • 逻辑思路：
    1、需要一个队列，用来遍历。 大数组：用来存所有遍历的数据，小数组用来存当前层的数据。
    2、每次遍历队列时：
               记录下当前队列长度（一层的数量）；
               定义当前小数组；
               每次都按照当前层的数量来进行遍历（处理当前层）；
                     每次弹出一个；
                     进行处理（推进小数组）；
                     将其左右推进队列；
               将小数组中的数组推进大数组；

LeetCode 102 二叉树的层序遍历 原题链接

  • 用队列来遍历，队列每次存的是当前这一层的数据量，然后每次按照当前层的数量来弹数据，并且处理数据。
class Solution {public:    queue<TreeNode*> q;    vector<vector<int>> res;    vector<vector<int>> levelOrder(TreeNode* root) { if (!root) return res; q.push(root); while (q.size()) {     int len = q.size();     vector<int> path;     while (len --)     {  auto t = q.front();  q.pop();  path.push_back(t->val);  if (t->left) q.push(t->left);  if (t->right) q.push(t->right);     }     res.push_back(path); } return res;    }};

LeetCode 107 二叉树的层序遍历II 原题链接

class Solution {public:    vector<vector<int>> res;    queue<TreeNode*> q;    vector<vector<int>> levelOrderBottom(TreeNode* root) { if (root) q.push(root); while (q.size()) {     vector<int> vec;     int len = q.size();     while (len --)     {  auto t = q.front();  vec.push_back(t->val);  q.pop();  if (t->left) q.push(t->left);  if (t->right) q.push(t->right);     }     res.push_back(vec); } reverse(res.begin(), res.end()); //反转即可 return res;    }};

LeetCode 199 二叉树的右视图 原题链接

  • 采用层序遍历，记录每层最右边的数即可。
class Solution {public:    queue<TreeNode*> q;    vector<int> res;    vector<int> rightSideView(TreeNode* root) { if (!root) return res; q.push(root); while (q.size()) {     int len = q.size();     for (int i = 0; i < len; i ++)     {  auto t = q.front();  q.pop();  if  (i == len - 1)      res.push_back(t->val);  if (t->left) q.push(t->left);  if (t->right) q.push(t->right);     } } return res;    }};

LeetCode 637 二叉树的层平均值 原题链接

  • 注意：不能用 while循环，因为 len --，之后长度就变了。
class Solution {    public:    queue<TreeNode*> q;    vector<double> res; vector<double> averageOfLevels(TreeNode* root) { if (root) q.push(root);  while (q.size()) {     int len = q.size();     double sum = 0;     while (len --)     {  auto t = q.front();   q.pop();  sum += t->val;  if (t->left) q.push(t->left);  if (t->right) q.push(t->right);     }     res.push_back(sum / len); }  return res;    }};
class Solution {public:    queue<TreeNode*> q;    vector<double> res;    vector<double> averageOfLevels(TreeNode* root) { if (!root) return res; q.push(root); while (q.size()) {     int len = q.size();     double sum = 0;     for (int i = 0; i < len; i ++) // 处理当前层     {  auto t = q.front();  q.pop();  sum += t->val;  if (t->left) q.push(t->left);  if (t->right) q.push(t->right);     }     res.push_back(sum / len); } return res;    }};

LeetCode 515 在每个树行中找最大值 原题链接

  • 层序遍历，取每行的最大值。
class Solution {public:    queue<TreeNode*> q;    vector<int> res;    vector<int> largestValues(TreeNode* root) { if (!root) return res; q.push(root); while (q.size()) {     int len = q.size();     int val = INT_MIN;     while (len --)     {  auto t = q.front();  q.pop();  val = max(val, t->val);  if (t->left) q.push(t->left);  if (t->right) q.push(t->right);     }     res.push_back(val); } return res;    }};

二叉搜索树题目汇总

LeetCode 98 验证二叉搜索树 原题链接

  • 二叉搜索树按照中序遍历的话是一个递增的序列。
class Solution {public:    TreeNode* pre = NULL;    bool isValidBST(TreeNode* root) { return dfs(root);    }    bool dfs(TreeNode* root)    { if (root == NULL) return true; auto left = dfs(root->left); if (pre && pre->val >= root->val) return false; pre = root; auto right = dfs(root->right); return left && right;    }};

LeetCode 108 将有序数组转换为二叉搜索树 原题链接

  • 一棵树是二叉搜索树等价于它的中序遍历是有序的；
  • 数组中间的位置作为树的根节点，然后递归处理左子树和右子树。
class Solution {public:    TreeNode* sortedArrayToBST(vector<int>& nums) { return build(nums, 0, nums.size() - 1);    }    TreeNode* build(vector<int>& nums, int l, int r)    { if (l > r) return NULL; int mid = l + r >> 1; auto node = new TreeNode(nums[mid]); node->left = build(nums, l, mid - 1); node->right = build(nums, mid + 1, r); return node;    }};

LeetCode 230 二叉搜索树中第k小的元素 原题链接

class Solution {public:    stack<TreeNode*> stk;    int kthSmallest(TreeNode* root, int k) { int count = 0; // 用遍历的方式 while (root || stk.size()) // 遍历树的结构 {     // 找到初始点     while (root)     {  stk.push(root);  root = root->left;     }   root = stk.top();     stk.pop();     count ++;     if (count == k)  return root->val;     root = root->right; } return root->val;    }};

LeetCode 700 二叉搜索树中的搜索 原题链接

class Solution {public:    TreeNode* searchBST(TreeNode* root, int val) { if (!root) return NULL; if (root->val == val) return root; else if (root->val > val) {     return searchBST(root->left, val); } else if (root->val < val) {     return searchBST(root->right, val); } return root;    }};
标签：