LeetCode Hot100 | Day5 | 二叉树右视图&&二叉树展开为链表

199.二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

完整代码：

1.递归遍历

来自于灵神的题解，我仅仅是看懂

遍历顺序：
中右左，因为收集的是右视图，我们要收集最右边的，先递归右子树，保证首次遇到的一定是最右边的，有人可能会好奇，这样的话，遍历左子树的时候会有不符合条件的答案进去，深度就是解决这个问题的

关键点：

深度首次遇到才会记录答案，这样避免了递归完右子树重新从根节点路过递归遍历左子树的时候，路过的重复深度的树层的树

这个在遍历完右子树后，如果左子树还有比右子树深度大的才会进入答案

class Solution {vector<int> ans;void dfs(TreeNode* node, int depth) {if (node == nullptr) {return;}if (depth == ans.size()) { // 这个深度首次遇到ans.push_back(node->val);}cout<<node->val<<endl;dfs(node->right, depth + 1); // 先递归右子树，保证首次遇到的一定是最右边的节点dfs(node->left, depth + 1);}public:vector<int> rightSideView(TreeNode* root) {dfs(root, 0);return ans;}
};

2.层序遍历

思路好想，代码也是模板，不多说了

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;queue<TreeNode*> q;if(root==nullptr)return res;q.push(root);while(!q.empty()){int size=q.size();vector<int> path;for(int i=0;i<size;i++){TreeNode *t=q.front();q.pop();path.push_back(t->val);if(t->left)q.push(t->left);if(t->right)q.push(t->right);}res.push_back(path);}return res;}
};

114.二叉树展开为链表

114. 二叉树展开为链表 - 力扣（LeetCode）

用一个vector把前序遍历结点存储一下，然后再把它串成链表

class Solution {
public:vector<TreeNode *> res;void tra(TreeNode *t){if(t==nullptr)return;res.push_back(t);tra(t->left);tra(t->right);}void flatten(TreeNode* root) {tra(root);for(int i=1;i<res.size();i++){res[i-1]->right=res[i];res[i-1]->left=nullptr;}return ;}
};