美国建设新闻网站/aso优化怎么做

前言

题目：257. 二叉树的所有路径

参考题解：二叉树的所有路径-力扣官方题解

提交代码

方法一：刚拿到这道题目的时候，我条件反射想到SMT-测试用例的自动生成，即翻转路径。首先，生成第一条路径：当存在左侧路径的时候，尽量向左走。之后，翻转路径的最后一位。迭代向上回溯。详细见下方代码。

方法二：第一种方法实现比较麻烦，我接着开始思考有没有其他解法。我发现，如果可以从根节点，向上回溯。当回溯到根节点时，即找见一条路径。每个叶子节点到根，即为一条路径。所以，我们只需要遍历一遍树，记录每个节点的父节点信息，并记录哪些是叶子节点，则很容易实现上面的方法。

第二种方法需要为每个节点和叶子节点创建附加空间。能否从上向下，直接查找呢。难处在于，在进入叉路的时候，如何动态的进行路径副本的拷贝。我没想出来，答案给了两种做法。

方法三：深度遍历。递归的时候，将路径作为函数参数，进行副本拷贝。这很好。

方法四：层次遍历。每个当前层节点有一条对应路径。路径执行和节点相同的操作。

翻转路径

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>#define null INT32_MIN  // 使用INT32_MIN代替nullusing namespace std;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:enum dirt{left,right,end};vector<string> binaryTreePaths(TreeNode* root) {vector<pair<dirt,dirt>> path_dirt; // 记录路径的方向，pair中存储<当前已走方向,待走方向>vector<int> path_int; // 记录路径的节点值vector<vector<int>> result_int;vector<string> result_string;if(root == nullptr)return result_string;// 得到第一条路径，当存在左孩子的时候，尽量向左孩子方向走TreeNode* node = root;path_int.push_back(node->val);while(node != nullptr){if(node ->left != nullptr && node->right != nullptr){node = node->left;path_dirt.push_back({left,right});path_int.push_back(node->val);}else if(node ->left != nullptr && node->right == nullptr){node = node->left;path_dirt.push_back({left,end});path_int.push_back(node->val);}else if(node ->left == nullptr && node->right != nullptr){node = node->right;path_dirt.push_back({right,end});path_int.push_back(node->val);}else{node = nullptr;}}result_int.push_back(path_int);// 当路径的最后一位是left，下一步为right。向right方向行走。// 当路径的最后一位的下一步是end，说明下一步无路可走，将其弹出// 直到最后路径为空while(!path_dirt.empty()){// 弹出路径尾部下一步为end的路径while( !path_dirt.empty() && path_dirt.back().second == end)path_dirt.pop_back();if(path_dirt.empty())break;// 路径的最后一条改为,向右走path_dirt[path_dirt.size()-1] = make_pair(right,end);TreeNode* node = root;path_int.clear();path_int.push_back(node->val);// 先走完path_dirt中既定的路线for(int i=0; i<path_dirt.size(); i++){ if(path_dirt[i].first==left){node = node->left;path_int.push_back(node->val);}else if(path_dirt[i].first == right){node = node->right;path_int.push_back(node->val);}}// 若后续路线存在，接着往下走while(node != nullptr){if(node ->left != nullptr && node->right != nullptr){node = node->left;path_dirt.push_back({left,right});path_int.push_back(node->val);}else if(node ->left != nullptr && node->right == nullptr){node = node->left;path_dirt.push_back({left,end});path_int.push_back(node->val);}else if(node ->left == nullptr && node->right != nullptr){node = node->right;path_dirt.push_back({right,end});path_int.push_back(node->val);}else{node = nullptr;}}          result_int.push_back(path_int);}// 将int的路径，转换成string的路径for(vector<int> path_int : result_int){string path_string;for(int val : path_int){path_string += to_string(val);path_string += "->";}path_string.pop_back();path_string.pop_back();result_string.push_back(path_string);}return result_string;}   
};class Tree{
private:TreeNode* root = nullptr;public:TreeNode* getRoot(){return root;}// 层次建立二叉树void buildTree(vector<int>& nums){const int len = nums.size();if(len == 0)return;root = new TreeNode(nums[0]);queue<pair<int,TreeNode*>> que; // 存储当前层节点信息：<数组中的下表，对于节点的地址>que.push(make_pair(0,root));while(!que.empty()){ // 层次遍历int que_size = que.size(); // 当前层节点个数for(int i=0; i<que_size; i++){pair<int,TreeNode*> nodePair = que.front();que.pop();int leftLoc = nodePair.first*2+1;int rightLoc = nodePair.first*2+2;if(leftLoc < len && nums[leftLoc] != null){ // 左节点存在TreeNode* node = new TreeNode(nums[leftLoc]);nodePair.second->left = node;que.push(make_pair(leftLoc,node));}if(rightLoc < len && nums[rightLoc] != null){ // 右节点存在TreeNode* node = new TreeNode(nums[rightLoc]);nodePair.second->right = node;que.push(make_pair(rightLoc,node));}}}}// 销毁二叉树void destroyTree(TreeNode* root){if(root!=nullptr){destroyTree(root->left);destroyTree(root->right);delete root;}}};int main(void){// 构建二叉树vector<int> nums = {1,2,3,null,5}; Tree tree;tree.buildTree(nums);// 查找二叉树的所有路径Solution s;vector<string> result = s.binaryTreePaths(tree.getRoot());for(auto num : result)cout<<num<<endl;// 销毁二叉树tree.destroyTree(tree.getRoot());
}

从叶子节点向上回溯

class Solution{
public:void recordParentAndLeaves(TreeNode* root, unordered_map<TreeNode*,TreeNode*>& child2parent, unordered_set<TreeNode*>& leaves){// 层次遍历二叉树，记录每个节点的父节点// 遇到叶子节点的时候，记录叶子节点if(root == nullptr)return;queue<TreeNode*> que;que.push(root);while(!que.empty()){int size = que.size();for(int i=0; i<size; i++){TreeNode* node = que.front();que.pop();if(node->left != nullptr){que.push(node->left);child2parent.emplace(make_pair(node->left,node));}if(node->right != nullptr){que.push(node->right);child2parent.emplace(make_pair(node->right,node));}if(node->left == nullptr && node->right == nullptr)leaves.insert(node);}}}vector<string> binaryTreePaths(TreeNode* root){unordered_map<TreeNode*,TreeNode*> child2parent;unordered_set<TreeNode*> leaves;recordParentAndLeaves(root,child2parent,leaves);vector<vector<int>> result_int;vector<string> result_string;vector<int> path_int;// 从叶子节点，溯源到根节点for(auto leaf : leaves){path_int.clear();path_int.push_back(leaf->val);TreeNode* node = leaf;while(child2parent.count(node)){node = child2parent[node];path_int.push_back(node->val);}reverse(path_int.begin(),path_int.end());result_int.push_back(path_int);}// 将int的路径，转换成string的路径for(vector<int> path_int : result_int){string path_string;for(int val : path_int){path_string += to_string(val);path_string += "->";}path_string.pop_back();path_string.pop_back();result_string.push_back(path_string);}return result_string;}
};

深度搜索-通过递归参数进行路径拷贝

class Solution {
public:void constructPAHT(TreeNode* root, vector<int> path, vector<vector<int>>& result_int){if(root == nullptr) // 遇到叶子是终止条件没错。这里习惯还是将遍历结束作为终止条件return;path.push_back(root->val); // 当前path副本，添加一个节点if(root->left == nullptr && root->right == nullptr) // 遇到叶子节点，即找到一条路径result_int.push_back(path);constructPAHT(root->left,path,result_int);constructPAHT(root->right,path,result_int);}vector<string> binaryTreePaths(TreeNode* root) {vector<vector<int>> result_int;vector<string> result_string;constructPAHT(root,{},result_int);// 将int的路径，转换成string的路径for(vector<int> path_int : result_int){string path_string;for(int val : path_int){path_string += to_string(val);path_string += "->";}path_string.pop_back();path_string.pop_back();result_string.push_back(path_string);}return result_string;}
};

层次遍历-每个当前层节点对应一条路径

class Solution {
public:vector<string> binaryTreePaths(TreeNode* root) {vector<vector<int>> result_int;vector<string> result_string;if(root == nullptr)return result_string;queue<TreeNode*> que_node;queue<vector<int>> que_path;que_node.push(root);que_path.push({root->val});while(!que_node.empty()){int size = que_node.size();for(int i=0; i<size; i++){ TreeNode* node = que_node.front();que_node.pop();vector<int> path = que_path.front();que_path.pop();if(node->left != nullptr){que_node.push(node->left);vector<int> new_path = path;new_path.push_back(node->left->val);que_path.push(new_path);}if(node->right != nullptr){que_node.push(node->right);vector<int> new_path = path;new_path.push_back(node->right->val);que_path.push(new_path);}if(node->left == nullptr && node->right == nullptr)result_int.push_back(path);}}// 将int的路径，转换成string的路径for(vector<int> path_int : result_int){string path_string;for(int val : path_int){path_string += to_string(val);path_string += "->";}path_string.pop_back();path_string.pop_back();result_string.push_back(path_string);}return result_string;}
};