算法（二叉树）

引言112. 路径总和 - 力扣LeetCode106. 从中序与后序遍历序列构造二叉树 - 力扣LeetCode617. 合并二叉树 - 力扣LeetCode98. 验证二叉搜索树 - 力扣LeetCode501. 二叉搜索树中的众数 - 力扣LeetCode236. 二叉树的最近公共祖先 - 力扣LeetCode第一题对于理解这一题我们主要的重点有两个一个是传递的参数我们这里传递的参数是count其作用主要是记录到每一个结点还需要的和。第二个是返回值我们可能有的时候是void有的时候又有返回值这其实取决于我们需不需要对于处理递归的返回值如果我们仅仅是计算高度其实用一个全局变量就可以了但是这一题我们需要判断路径当一个结点返回true的时候说明已经找到了路径那么就可以把true向上传递返回。而传递这个返回值我们就必须要接受这个返回值这里用的是if如果返回的是int那么我们就需要用int来接受。其他的思路就比较的简单就是在回溯的前面查看一下返回值是不是true如果是的就没必要回溯然后往其他的地方去遍历直接返回。当然如果我们提供的三个返回true的地方都没有返回true说明这个结点就是false那么我们在最后就是return false/** * 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 traversal(TreeNode* cur, int count) { if (!cur-left !cur-right count 0) { return true; } if (!cur-left !cur-right) { return false; } if (cur-left) { count - cur-left-val; if (traversal(cur-left, count)) { return true; } count cur-left-val; } if (cur-right) { count - cur-right-val; if (traversal(cur-right, count)) { return true; } count cur-right-val; } return false; } bool hasPathSum(TreeNode* root, int targetSum) { if (root nullptr) { return false; } return traversal(root, targetSum - root-val); } };第二题通过中序遍历和后序遍历来构造一棵二叉树这十分的考验我们对二叉树的理解。首先中序遍历最大的优势就是如果我们确定了根节点那么我们就可以把一棵树分成左右两颗树而前序遍历和后续遍历的优势就是找到根节点。所以我们先从后续遍历找到根节点然后构造出来再根据值在中序遍历里面找到其对应的位置然后把中序和后续数组分成左右两个部分就这么一直循环直到分到最后一个然后一个一个的回溯把结点不停的传到root-left或者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: TreeNode* traversal (vectorint inorder, vectorint postorder){ if (postorder.size() 0) { return nullptr; } int rootValue postorder[postorder.size() - 1]; TreeNode* newNode new TreeNode(rootValue); if (postorder.size() 1) { return newNode; } int index 0; for (int i 0; i inorder.size(); i) { if (rootValue inorder[i]) { index i; break; } } vectorint leftInorder(inorder.begin(), inorder.begin() index); vectorint rightInorder(inorder.begin() index 1, inorder.end()); postorder.resize(postorder.size() - 1); vectorint leftPostorder(postorder.begin(), postorder.begin() leftInorder.size()); vectorint rightPostorder(postorder.begin() leftInorder.size(), postorder.end()); newNode-left traversal(leftInorder, leftPostorder); newNode-right traversal(rightInorder, rightPostorder); return newNode; } TreeNode* buildTree(vectorint inorder, vectorint postorder) { if (inorder.size() 0 || postorder.size() 0) return NULL; return traversal(inorder, postorder); } };第三题这是一个对两个二叉树同时操作的题目这一题的一个难点是如果a树没有的结点b树有我们应该怎么加上去如果b树没有的a树有怎么办我们可以在一开始就做一个判断如果a树没有那么就返回b树的结点如果b树没有那么就返回a树的如果都没有那么也返回b树的其实也就是nullptr。然后我们直接在a树上改造就可以。同时操作二叉树的关键就是我们每一次都要传递两个树的参数保证两个树的同步性/** * 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* mergeTrees(TreeNode* root1, TreeNode* root2) { if (root1 nullptr) { return root2; } if (root2 nullptr) { return root1; } root1-val root2-val; root1-left mergeTrees(root1-left, root2-left); root1-right mergeTrees(root1-right, root2-right); return root1; } };第四题这一题我选择的是双指针的方法这里有几个细节需要注意就是我们只有遇到了空结点或者两个子树全部都是true我们才会返回true千万不可以在中途就返回true这样会导致漏掉情况。反而只要有情况不符合直接返回false。/** * 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* pre nullptr; bool isValidBST(TreeNode* root) { if (root nullptr) { return true; } bool left isValidBST(root-left); if (pre pre-val root-val) { return false; } pre root; bool right isValidBST(root-right); return left right; } };第五题这一题我们有一个比较简单的思路因为这个是搜索二叉树所以我们中序遍历的特点就是如果又相同的数那么一定是会挨在一起的所以我们其实只需要记录每一次出现的最高频率如果之后的频率和这个一样那么就把这个数加入数组之中如果超过了那么我们就把数组清空更新一下最高频率再把这个数放入我们新的数组之中。同时每一次遇到新的数我们也要重置一下cnt的值计为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 cnt 0; TreeNode* pre nullptr; vectorint res; int maxCount 0; vectorint findMode(TreeNode* root) { if (root nullptr) { return res; } findMode(root-left); if (pre nullptr) { cnt 1; }else if (pre ! nullptr root-val pre-val) { cnt; } else { cnt 1; } pre root; if (cnt maxCount) { res.push_back(root-val); } if (cnt maxCount) { res.clear(); maxCount cnt; res.push_back(root-val); } findMode(root-right); return res; } };第六题最近的公共祖先它的关键点就是如果找到了结点那么就一层一层的返回。而从底到根的遍历方式只有后序遍历对于一个结点是不是返回返回什么取决于它的左子树和右子树返回的值。不过我还想强调一个就是关于我们处理结点的地方处理结点的地方即使是后序遍历可能大家也发现了有的会放在前面这个是我们对一个结点的最开始的判断并不是后序遍历的那个对根节点的处理。最开始的if判断是确定我们什么时候返回而真正对根节点的操作是决定返回什么值。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root NULL) { return root; } if (root p || root q) { return root; } TreeNode* left lowestCommonAncestor(root-left, p, q); TreeNode* right lowestCommonAncestor(root-right, p, q); if (left ! nullptr right ! nullptr) { return root; } else if (left ! nullptr right nullptr) { return left; } else if (left nullptr right ! nullptr) { return right; } else { return nullptr; } } };总结本篇文章主要是针对递归的方式进行算法分析希望可以帮助到大家~~~