二叉树的左视图

2025年3月17日 | 阅读 3 分钟

二叉树的左视图是由各层最左边的节点组成的集合。

示例

输入

输出

4 5 3 6

方法 1：迭代实现

在迭代版本中执行树的层序遍历。为了保留当前层级的节点，我们可以改变层序遍历。如果当前节点是当前层级的第一个节点，则打印它。

方法 2：使用递归

该方法是使用递归来查找二叉树的左视图。可以将一个参数传递给所有递归调用，以确定节点的级别。当我们遇到一个级别高于迄今为止找到的最高级别的节点时，我们显示它。这是因为它是在此级别遇到的第一个节点。为了显示二叉树的左视图，我们必须以先访问左子树再访问右子树的方式进行遍历。

程序

// A Recursive function to print the nodes
// of left view of a binary tree.

void leftViewUtil(Node node, int level)
    {
        // Base Case
        if (node == null)
            return;

        // If this is the left most Node of its level
        if (max_level < level) {
            System.out.print(" " + node.val);
            max_level = level;
        }

        // Recur call for left subtree first,
          // then right subtree
        leftViewUtil(node.left, level + 1);
        leftViewUtil(node.right, level + 1);
    }

输出

 The following are the nodes present in the left view of the Binary Tree: 
20 22 25 14 7

在递归实现中也可以使用哈希。

我们也可以使用哈希来解决这个问题。计划是执行树的先序遍历，同时传递带有级别信息的函数参数。如果某个级别是第一次访问，则将当前节点和级别的信息添加到映射中。处理完每个节点后，导航映射并打印左视图。

程序

C++

/* A binary tree node

struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
    
    Node(int x){
        data = x;
        left = right = NULL;
    }
};
 */

//Function to return a list containing elements of left view of the binary tree.
vector<int> leftView(Node *root)
{
    
   vector<int>v;
    if(root==NULL){
       
       return v;
       // for returning empty vector just simply return it
    }
   
   queue<Node*>q;
   q.push(root);
   
   while(q.size()>0){
      int count=q.size();
       
       
       for(int i=0;i<count;i++){
       Node*curr=q.front();
       q.pop();
           
          if(i==0){ v.push_back(curr->data);}
          
          if(curr->left!=NULL){
              q.push(curr->left);
          }
          if(curr->right!=NULL){
              q.push(curr->right);
          }
       }
       
    // code is similar to level order transversal but only at i==0 it will push in vector/print on screen   
       
       
   }
      return v; 
   }

Java

/* A Binary Tree node
class Node
{
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}*/


class TreeNodeInfo5
{
    // For Left and Right View Traversal
    Node node;
    int level;

    public TreeNodeInfo5(Node node, int level)
    {
        this.node = node;
        this.level = level;
    }
}

class Tree
{
    //Function to return list containing elements of left view of binary tree.
    ArrayList<Integer> leftView(Node root)
    {
        return leftViewTraversal2(root);
    }
    
    private static ArrayList<Integer> leftViewTraversal2(Node root)
    {
        /*
            TC: O(n)
            SC: O(n)
         */
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null) { return res; }

        HashMap<Integer, Integer> leftView = new HashMap<>();

        leftViewTraversalHelper(root, 1, leftView);

        for(int i=1; i<=leftView.size(); i++)
        {
            res.add(leftView.get(i));
        }

        return res;
    }

    private static void leftViewTraversalHelper(Node root, int level, HashMap<Integer, Integer> leftView)
    {
        if(root == null) { return; }

        leftView.put(level, root.data);
        leftViewTraversalHelper(root.right, level+1, leftView);
        leftViewTraversalHelper(root.left, level+1, leftView);
    }
}

输出

对于以下输入

   1
 /  \
3    2

输出是：1 3

什么是层序遍历？

逐层遍历树的过程称为层序遍历。

我们可以使用先序遍历来查找二叉树的左视图吗？

是的，我们只需要跟踪节点的当前高度，如果我们第一次访问某个高度，我们将打印出该元素。

因此，二叉树的左视图既可以通过迭代方式也可以通过递归方式实现。

下一个主题二叉树的层序遍历

← 上一个下一个 →

二叉树的左视图

示例

方法 1：迭代实现

方法 2：使用递归

程序

在递归实现中也可以使用哈希。

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

二叉树的左视图

示例

方法 1：迭代实现

方法 2：使用递归

程序

在递归实现中也可以使用哈希。

程序

相关帖子

创建具有 O 和 X 交替矩形的矩阵

检查字符串的某个回文排列是否存在

数组是最好的数据结构

自平衡二叉搜索树

检查两个数组是否相等

线索二叉树

二叉树的性质

数据结构中栈的入栈和出栈操作

树遍历

矩阵沿对角线镜像

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器