问二叉树的左视图
EN

Stack Overflow用户

提问于 2022-08-29 20:33:02

回答 2查看 72关注 0票数 1

若要查找从二叉树左侧可见的所有节点集，请执行以下操作。

   vector<int> getLeftView(TreeNode<int> *root)
    {
         static vector<int> res;
       // Your code here
       if(root){
           res.push_back(root->data);
           if(root->left)
                getLeftView(root->left);
           else
                getLeftView(root->right);
       }
       return res;
}

对于单个测试用例，一次工作很好。但是，当运行多个测试用例时，向量中的前一个值将被新值追加。在运行下一个测试用例之前，如何清除向量？

c++

data-structures

binary-tree

回答 2

Stack Overflow用户

回答已采纳

发布于 2022-08-29 20:39:26

使用static是因为需要跨递归使用向量的单个实例。但是static不是方法，它导致整个程序中只有一个向量的实例。

有多种解决方案，其中之一是将函数拆分为API和递归部分：

void getLeftViewRec(TreeNode<int> *root, vector<int> &res)
{
    if(root){
        res.push_back(root->data);
        if(root->left)
             getLeftView(root->left, res);
        else
             getLeftView(root->right, res);
    }
    return res;
}


vector<int> getLeftView(TreeNode<int> *root)
{
    vector<int> res;
    getLeftViewRec(root, res);
    return res;
}

现在发生的情况是，每次调用getLeftView时，都会将一个新的向量res实例化为局部变量。然后，它调用递归函数getLeftViewRec，该函数通过引用接收res，并通过递归调用将其传递给自己，因此递归处理一个向量，并将其累加到其中。

票数 1

Stack Overflow用户

发布于 2022-08-29 20:40:48

使用队列和空指针标记每个级别的第一个元素。我们在第一个中插入一个空指针，当到达这个空指针时，我们将bool标记为true并将下一个元素作为我们的左视图元素，

// C++ Code for the above iterative approach
#include <bits/stdc++.h>
using namespace std;

// Tree Node Structure contains data, left and right
// pointer
struct Node {
    int data;
    struct Node *left, *right;
};

// A utility function to
// create a new Binary Tree Node
struct Node* newNode(int item)
{
    struct Node* temp
        = (struct Node*)malloc(sizeof(struct Node));
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}

// function to get the left view of binary tree in vector
vector<int> leftView(Node* root)
{

    // store the left view
    vector<int> ans;

    // Base Case : Empty Tree
    if (!root)
        return ans;
    

    // Create an empty queue and enque root node and null
    queue<Node*> q;
    q.push(root);
    q.push(NULL);
    bool ok = true;

    // Traverse till queue is not empty
    while (!q.empty()) {
        // get the front node and dequeue it from queue
        auto it = q.front();
        q.pop();

        // if the front node is null do following steps
        if (it == NULL) {
            if (ok == false)
                ok = true;
            

            if (q.size() == 0)
                break;
            
            else
                q.push(NULL);
            
        }
        // else do the following steps
        else {
            if (ok) {
                ans.push_back(it->data);
                ok = false;
            }

            if (it->left)
                q.push(it->left);
            
            if (it->right)
                q.push(it->right);
            
        }
    }

    // return the left view
    return ans;
}

// driver code to test above code on a test case
int main()
{
    /*
    Input :
                10
                / \
                2    3
            / \ / \
            7 8 12 15
                        /
                        14

    Output : 10 2 7 14
*/
    // let's build above shown tree
    Node* root = newNode(10);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(7);
    root->left->right = newNode(8);
    root->right->right = newNode(15);
    root->right->left = newNode(12);
    root->right->right->left = newNode(14);

    // call leftview function and store output in vec
    vector<int> vec = leftView(root);
    // traverse on left view and print each element
    for (int x : vec)
        cout << x << " ";
    cout << endl;

    return 0;
}