Day21-二叉树-二叉树的右视图

BUPTrenyi

发布于 2019-07-15 17:03:10

6040

发布于 2019-07-15 17:03:10

文章被收录于专栏：算法其实很好玩

一唠嗑

我尽量加快进度，明天开始讲图。

二叉树没了？当然不是，难题后面会慢慢更的

二上题

Q：给定一个二叉树，以从上到下的顺序，返回这个二叉树的右视图。

举例：还是昨天的二叉树

那么就要返回数组[1，5，6]

如果此时把6节点拿掉，就要返回[1，5，4]

三冷静分析

此处我们先复习一下二叉树的层次遍历

思路很简单，利用队列（FIFO的性质）

将二叉树根节点push进队列

在队列非空的情况下循环：

取出队头元素，并输出；

弹出刚刚输出的队头元素；

将队头的左子树push进队列（如果有左子树）；

将队头的右子树push进队列（如果有右子树）；

逻辑很简单，主要是利用了队列先进先出的性质来实现层次遍历。直接上代码

//
// Created by renyi on 2019-07-09.
//
#include <iostream>
#include <queue>
using namespace std;

struct TreeNode{
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : value(v), left(NULL), right(NULL) {}
};

void levelTraversalPrint(TreeNode* root){
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()){
        TreeNode* node = q.front();//取出队头元素
        printf("[%d]", node->value);
        q.pop();

        if (node->left){
            q.push(node->left);
        }

        if (node->right){
            q.push(node->right);
        }
    }
}

int main(){
    TreeNode a(1);//建立配图的二叉树
    TreeNode b(2);
    TreeNode c(5);
    TreeNode d(3);
    TreeNode e(4);
    TreeNode f(6);

    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;

    levelTraversalPrint(&a);
    return 0;
}

那么对于这个二叉树，层次遍历的结果就应该是

回到题目本身，我们需要利用层次遍历的思想来解决它：

层次遍历二叉树
建立数组view保存最后结果，建立队列q保存<节点指针，高度>这样绑定的数据（可以稍微看一下pair的用法，不难，很好理解）
以根节点的高度为0开始，当数组的size()和高度相同时，此时我们需要把节点添加进数组中。当两者不相同时，此时我们需要更新以高度为下标的数组的值，来保证，view里存储的都是各个层最右边的节点。
最终view存储的就是各个层最右边的节点，返回即可。

以图示二叉树举例说明：

view[0] = 1

view[1] = 2

接下来遍历到5节点，这时高度还是1，但数组的size（）为2，二者并不相同了，所以要更新view数组，来保证存储的是最右边的节点。

view[1] = 5

接下来遍历3节点，此时高度为2，view的size（）也是2，所以向数组插入数据

view[2] = 3

接下来遍历的节点，高度和size又不再相同了，此时需要更新view保证是最右边的节点，以此类推。

主要思路是层次遍历的思路+对关键节点的判断

四完整代码及注释

//
// Created by renyi on 2019-07-09.
//
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode{
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : value(v), left(NULL), right(NULL) {}
};

vector<int> rightSideViewTree(TreeNode* root){
    vector<int> view;//建立数组view，保存二叉树的各层最右边的节点
    queue<pair<TreeNode*, int>> q;//建立队列q，保存<节点，层数>绑定在一起的数据

    if (root){//当根节点非空时，将<root, 0>push进入队列
        q.push(make_pair(root, 0));
    }

    while (!q.empty()){//当队列非空时，一直循环
        TreeNode* node = q.front().first;//取队头的第一个元素，第一次取，就是根节点指针root
        int depth = q.front().second;//取队头第二个元素，第一次取，就是根节点高度，就是0
        q.pop();

        if (view.size() == depth){//当view.size()=高度depth时，说明又往深遍历了一层，此时要往view中添加节点
            view.push_back(node->value);
        } else{//只要不相等，说明遍历的节点还在同一层，更新下标为depth的值，即更新更靠右的节点值
            view[depth] = node->value;
        }

        if (node->left){//层次遍历，将左右子树添加进队列，同时高度+1
            q.push(make_pair(node->left, depth+1));
        }
        if (node->right){
            q.push(make_pair(node->right, depth+1));
        }
    }
    return view;
}

int main(){
    TreeNode a(1);//建立配图的二叉树
    TreeNode b(2);
    TreeNode c(5);
    TreeNode d(3);
    TreeNode e(4);
    //TreeNode f(6);

    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    //c.right = &f;

    vector<int> result = rightSideViewTree(&a);
    for (int i = 0; i < result.size(); i++) {
        printf("[%d]", result[i]);
    }
    printf("\n");
    return 0;
}

代码中，是为了测试去掉节点6的运行结果