关于树的算法题总结

目录437. 路径总和 III - 力扣LeetCode105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode103. 二叉树的锯齿形层序遍历 - 力扣LeetCode230. 二叉搜索树中第 K 小的元素 - 力扣LeetCode437. 路径总和 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(rootnullptr) return; if(targetSum-root-val0) cnt; dfs(root-left, targetSum-root-val); dfs(root-right, targetSum-root-val); } int pathSum(TreeNode* root, int targetSum) { if(rootnullptr) 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(vectorint preorder, vectorint inorder) { if(preorder.empty()) return nullptr; TreeNode* res new TreeNode(preorder[0]); vectorint inleft; vectorint inright; int inflag 0; for(int i : inorder){ if(ires-val){ inflag1; continue; } if(inflag0) inleft.push_back(i); else inright.push_back(i); } //只要我们在中序遍历中定位到根节点 //那么我们就可以分别知道左子树和右子树中的节点数目 vectorint preleft; vectorint preright; for(int i 1; ipreorder.size(); i){ if(iinleft.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: vectorvectorint zigzagLevelOrder(TreeNode* root) { //思路就是基于队列的BFS vectorvectorint res; queueTreeNode* qe; if(root!nullptr) qe.push(root); while(!qe.empty()){ vectorint level; int n qe.size(); for(int i 0; in; 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()11) 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(rootnullptr) return 0; kthSmallest(root-left, k); if(cnt!-1) cnt; if(cntk){ res root-val; cnt -1; } kthSmallest(root-right, k); return res; } }; /* 非递归的中序遍历也很重要 class Solution { public: int kthSmallest(TreeNode* root, int k) { stackTreeNode * 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) { stackTreeNode* nodes; while(root!nullptr){ nodes.push(root); root root-left; } while(!nodes.empty()){ TreeNode* r nodes.top(); nodes.pop(); k--; if(k0) return r-val; //如果r有右子树的话 if(r-right!nullptr){ TreeNode* p r-right; while(p!nullptr){ nodes.push(p); p p-left; } } } return -1; } };