题目链接

LeetCode

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

解题思路

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

• 二叉树的节点个数的范围是 [0,100]

• -100 <= Node.val <= 100
  

  方法一：bfs

  /**
  * 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:
    vector<int> rightSideView(TreeNode* root) {
        if(root==nullptr){
            return {};
        }
        deque<TreeNode*> dq;
        vector<int> ans;
        dq.push_front(root);
        while(!dq.empty()){
            ans.push_back(dq.back()->val);
            int k = dq.size();
            while(k--){
                TreeNode* tmp = dq.back();
                dq.pop_back();
                if(tmp->right){
                    dq.push_front(tmp->right);
                }
                if(tmp->left){
                    dq.push_front(tmp->left);
                }
            }
        }
        return ans;
    }
  };

• 时间复杂度 O(n)

• 空间复杂度 O(n)

  方法二：自定义数据结构bfs

  /**
  * 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 {
  private:
    // 自定义双向链表
    struct TreeList{
        TreeNode* node;
        TreeList* pre;
        TreeList* next;
        TreeList(){
            pre = nullptr;
            next = nullptr;
            node = nullptr;
        }
        TreeList(TreeNode* n){
            pre = nullptr;
            next = nullptr;
            node = n;
        }
    };
    // 双向链表的头和尾
    TreeList* head = new TreeList();
    TreeList* tail = new TreeList();
  public:
    vector<int> rightSideView(TreeNode* root) {
        if(root==nullptr){
            return {};
        }
        vector<int> ans;
        // 加入链表
        TreeList* node = new TreeList(root);
        head->next = node;
        node->pre = head;
        node->next = tail;
        tail->pre = node;
        // sz表示当前链表中节点的个数
        int sz = 1;
        // head->next!=tail当前链表中不为空
        while(head->next!=tail){
            // 将链表最后一个节点的值加入结果
            ans.push_back(tail->pre->node->val);
            int k = sz;
            while(k--){
                // 在链表中删除最右边的节点
                TreeList* tmp = tail->pre;
                tail->pre = tail->pre->pre;
                tail->pre->next = tail;
                sz--;
                // 如果链表最右边节点有右节点，用头插法加入链表
                if(tmp->node->right){
                    TreeList* node = new TreeList(tmp->node->right);
                    node->next = head->next;
                    head->next->pre = node;
                    head->next = node;
                    node->pre = head;
                    sz++;
                }
                // 如果链表最右边节点有左节点，用头插法加入链表
                if(tmp->node->left){
                    TreeList* node = new TreeList(tmp->node->left);
                    node->next = head->next;
                    head->next->pre = node;
                    head->next = node;
                    node->pre = head;
                    sz++;
                }
            }
        }
        return ans;
    }
  };

• 时间复杂度 O(n)

• 空间复杂度 O(n)