算法（二叉树）-Seo优化-塔城地区网站建设公司

引言

112. 路径总和 - 力扣（LeetCode）

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

617. 合并二叉树 - 力扣（LeetCode）

98. 验证二叉搜索树 - 力扣（LeetCode）

501. 二叉搜索树中的众数 - 力扣（LeetCode）

236. 二叉树的最近公共祖先 - 力扣（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 (vector<int>& inorder, vector<int>& 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; } } vector<int> leftInorder(inorder.begin(), inorder.begin() + index); vector<int> rightInorder(inorder.begin() + index + 1, inorder.end()); postorder.resize(postorder.size() - 1); vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size()); vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end()); newNode->left = traversal(leftInorder, leftPostorder); newNode->right = traversal(rightInorder, rightPostorder); return newNode; } TreeNode* buildTree(vector<int>& inorder, vector<int>& 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; vector<int> res; int maxCount = 0; vector<int> 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; } } };