[leetcode]199-二叉树的右视图

马谦马谦马谦

615
文章

17
评论

2020年4月16日22:18:56数据结构和算法评论299字数 487阅读1分37秒阅读模式

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-tree-right-side-view

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

示例：

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

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

1 <---

/ \

2 3 <---

\ \

5 4 <---

二、题解

2.1 广度优先遍历

看到题目第一个想到的就是广度优先遍历，因为右视图看到的都是每一层最右边的节点，直接通过广搜层次遍历，然后取每层最后的元素即可。

2.2 深搜+递归

深搜的过程：一直读右子树的节点，直到右子树不存在，然后遍历左子树。同时，给每层数据都加上层数标记，因为遍历了右子树后还需要遍历左子树，如果当前层已经找过到了最右边的节点，就继续往下找。

[leetcode]199-二叉树的右视图

三、代码

广搜代码

class Solution {
public:
    vector<int> rightSideView(TreeNode *root) {
        int i, n;
        queue<TreeNode *> q;
        TreeNode *p;
        vector<int> ans;

        if (root == nullptr) {
            return ans;
        }

        q.push(root);

        while (!q.empty()) {
            n = q.size();

            for (i = 0; i < n; i++) {
                p = q.front();
                q.pop();
                if (p->left)
                    q.push(p->left);
                if (p->right)
                    q.push(p->right);
            }

            ans.push_back(p->val);
        }

        return ans;
    }
};

class Solution {

public:

vector<int> rightSideView(TreeNode *root) {

int i, n;

queue<TreeNode *> q;

TreeNode *p;

vector<int> ans;

if (root == nullptr) {

return ans;

}

q.push(root);

while (!q.empty()) {

n = q.size();

for (i = 0; i < n; i++) {

p = q.front();

q.pop();

if (p->left)

q.push(p->left);

if (p->right)

q.push(p->right);

}

ans.push_back(p->val);

}

return ans;

}

};

深搜代码

class Solution {
private:
    void f(vector<int> &ans, int depth, TreeNode *root) {
        TreeNode *p;
        int n;

        if (root == nullptr)
            return;

        if (ans.size() <= depth) {
            ans.push_back(root->val);
        }

        if (root->right) {
            f(ans, depth + 1, root->right);
        }
        if (root->left) {
            f(ans, depth + 1, root->left);
        }
    }
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        f(ans, 0, root);
        return ans;
    }
};