问二叉树的左视图

EN

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

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