关于树的算法题总结

目录

437. 路径总和 III - 力扣（LeetCode）

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

437. 路径总和 III - 力扣（LeetCode）

中等 通过率 48.3%

核心思想：

为了求该二叉树里节点值之和等于targetSum的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

我们很容易可以想到用DFS去遍历所有节点，当节点值之和等于targetSum时就cnt++。

但是为了找到所有的路径，我们还需要从不同的节点开始做DFS。

属于是DFS里面套了一个DFS。

/** * 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: //属于是对每一个结点都做一次DFS int cnt = 0; void dfs(TreeNode* root, long long targetSum){ if(root==nullptr) return; if(targetSum-root->val==0) cnt++; dfs(root->left, targetSum-root->val); dfs(root->right, targetSum-root->val); } int pathSum(TreeNode* root, int targetSum) { if(root==nullptr) return cnt; //属于是DFS里面再套一个DFS 真暴力！ dfs(root, targetSum); pathSum(root->left, targetSum); pathSum(root->right, targetSum); return cnt; } };

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

中等 通过率 73.2%

核心思想：

1. 写一个函数buildTree可以基于树的前序和树的中序找到树的根root和左右子树的前中序

2. 递归这个buildTree函数

root->left = buildTree(左子树的前序，左子树的中序)

root->right = buildTree(右子树的前序，右子树的中序)

/** * 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: //preorder 和 inorder 均 无重复 元素 //首先根据preorder拿到根root //然后再根据根凑够inorder里面找到左右子树 inleft 和 inright //重点：然后基于左右子树的数量，可以去preorder里面找到 preleft 和 preright //那么问题又变成了在root的左右子树里面找左右子树，发现任务与之前是一样的 //所以采用递归实现！ TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.empty()) return nullptr; TreeNode* res = new TreeNode(preorder[0]); vector<int> inleft; vector<int> inright; int inflag = 0; for(int i : inorder){ if(i==res->val){ inflag=1; continue; } if(inflag==0) inleft.push_back(i); else inright.push_back(i); } //只要我们在中序遍历中定位到根节点， //那么我们就可以分别知道左子树和右子树中的节点数目 vector<int> preleft; vector<int> preright; for(int i = 1; i<preorder.size(); i++){ if(i<=inleft.size()){ preleft.push_back(preorder[i]); }else preright.push_back(preorder[i]); } res->left = buildTree(preleft, inleft); res->right = buildTree(preright, inright); return res; } };

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

中等 通过率 60.7%

核心思想：本质就是层序遍历，只不过偶数层不变，奇数层逆序。

/** * 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>> zigzagLevelOrder(TreeNode* root) { //思路就是基于队列的BFS vector<vector<int>> res; queue<TreeNode*> qe; if(root!=nullptr) qe.push(root); while(!qe.empty()){ vector<int> level; int n = qe.size(); for(int i = 0; i<n; i++){ TreeNode* now = qe.front(); level.push_back(now->val); qe.pop(); if(now->left!=nullptr) qe.push(now->left); if(now->right!=nullptr) qe.push(now->right); } //只不过最后push_back的时候做个判断如果是奇数层就reverse一下 if(res.size()&1==1) reverse(level.begin(), level.end()); res.push_back(level); } return res; } };

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

中等 通过率 79.8%

核心思想：因为二叉搜素树的中序遍历是有序的，所以我们在进行中序遍历的时候，用cnt记录一下现在遍历了几个结点了，如果遍历到了低k小的结点就return就好了。

/** * 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 cnt = 0; int res = 0; int kthSmallest(TreeNode* root, int k) { if(root==nullptr) return 0; kthSmallest(root->left, k); if(cnt!=-1) cnt++; if(cnt>=k){ res = root->val; cnt = -1; } kthSmallest(root->right, k); return res; } }; /* 非递归的中序遍历也很重要 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(); // 等价于输出（左节点或根节点） --k; if (k == 0) { break; } root = root->right; //然后再来看右边的结点 } return root->val; } }; */ class Solution { public: int kthSmallest(TreeNode* root, int k) { stack<TreeNode*> nodes; while(root!=nullptr){ nodes.push(root); root = root->left; } while(!nodes.empty()){ TreeNode* r = nodes.top(); nodes.pop(); k--; if(k==0) return r->val; //如果r有右子树的话 if(r->right!=nullptr){ TreeNode* p = r->right; while(p!=nullptr){ nodes.push(p); p = p->left; } } } return -1; } };