LeetCode Hot100 | Day5 | 二进制树右视图 && 二进制树扩展为链式列表

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 ;
    }
};