在C语言中打印二叉树的左视图

什么是二叉树？

在计算机科学中，二叉树（Binary tree）是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

对二叉树的每个节点来说，都有一个值和指向左右子树的指针。指针为空的节点被称作叶子节点。

相对于数组和链表，二叉树的插入、删除、查找操作更加高效。

什么是二叉树的左视图？

二叉树的左视图，指的是从二叉树的左侧观察，看到的所有节点的值。

我们也可以理解为，从根节点开始，只要该节点在某一层次没有被看到过，那么这个节点在左侧就是可以看到的。

下面我们来看如何在C语言中打印出二叉树的左视图。

如何实现二叉树的左视图？

思路一：利用先序遍历实现

利用二叉树的先序遍历（根结点 -> 左子树 -> 右子树），可以实现打印二叉树的左视图。通过记录二叉树的深度，如果当前节点深度大于结果数组的深度，则直接将节点的值存入结果数组，并更新结果数组深度。

我们可以使用递归的方式实现先序遍历：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void dfs(struct TreeNode* root, int depth, int* res, int* max_depth)
{
    if (root == NULL) {
        return;
    }
    if (depth > *max_depth) {
        *res = root->val;
        *max_depth = depth;
    }
    dfs(root->left, depth + 1, res, max_depth);
    dfs(root->right, depth + 1, res, max_depth);
}
int* rightSideView(struct TreeNode* root, int* returnSize){
    int* res = (int*)malloc(sizeof(int) * 1000);
    int max_depth = -1;
    dfs(root, 0, res, &max_depth);
    *returnSize = max_depth + 1;
    return res;
}

时间复杂度：O(n)。

空间复杂度：O(h)，其中 h 是树的高度。使用的最大递归深度等于树的高度。

思路二：利用队列实现

我们也可以使用 BFS（广度优先遍历）的方式实现二叉树的左视图。使用队列记录每一层的节点，只需要保留队列尾部（即右侧）的节点的值，就可以得到二叉树的左视图。

typedef struct Queue {
    TreeNode* data;
    struct Queue* next;
}Queue;
Queue* queueCreate(TreeNode* data) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->data = data;
    queue->next = NULL;
    return queue;
}
void enQueue(Queue* queue, TreeNode* data) {
    Queue* newNode = queueCreate(data);
    queue->next = newNode;
    queue = newNode;
}
TreeNode* deQueue(Queue* queue) {
    if (queue == NULL || queue->next == NULL) {
        return NULL;
    }
    TreeNode* res = queue->next->data;
    Queue* delNode = queue->next;
    queue->next = queue->next->next; 
    free(delNode);
    return res;
}
int* rightSideView(struct TreeNode* root, int* returnSize){
    int *res = (int*)malloc(sizeof(int) * 1000);
    int k = 0;
    Queue* queue = queueCreate(NULL);
    TreeNode* temp;
    if (root == NULL) {
        *returnSize = 0;
        return res;
    }
    enQueue(queue, root);
    while(queue->next) {
        int size = queue->next - queue;
        for (int i = 0; i < size; ++i) {
            temp = deQueue(queue);
            if (temp->left != NULL) {
                enQueue(queue, temp->left);
            }
            if (temp->right != NULL) {
                enQueue(queue, temp->right);
            }
            if (i == size - 1) {
                res[k++] = temp->val;
            }
        }
    }
    *returnSize = k;
    return res;
}

时间复杂度：O(n)。

空间复杂度：O(n)

总结

本篇文章介绍了二叉树的概念、二叉树的左视图的定义以及两种方法实现打印出二叉树的左视图。递归和非递归的方式都需要掌握，作为算法中的经典问题，理解二叉树和掌握二叉树的相关操作是计算机科学与技术学习的基础。