根到叶子节点路径上不同节点的数量最多

2024 年 8 月 28 日 | 阅读 2 分钟

找出给定二叉树所有从根到叶子节点的路径上不同节点的最多数量。

示例

Input :   1
            /    \
           2      3
          / \    / \
        4   5  6   3
               \   \
                8   9 

Output : 4 
The root to leaf path with maximum distinct
nodes is 1-3-6-8.

遍历所有从根到叶子节点的路径是一个简单的解决方案。计算每条从根到叶子节点的路径上的不同节点数量，并返回最大值。

哈希是一种有效的解决方案。我们递归地遍历树，跟踪从根到当前节点的路径上不同节点的数量。我们为左右子树重复此操作，并返回两个值中的最大值。

上述思路的实现如下所示。

C++ 程序

// C++ program to find count of distinct nodes
// on a path with maximum distinct nodes.
#include <bits/stdc++.h>
using namespace std;

// A node of binary tree
struct Node {
	int data;
	struct Node *left, *right;
};

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

int largestUinquePathUtil(Node* node, unordered_map<int, int> m)
{
	if (!node)
		return m.size();

	// put this node into hash
	m[node->data]++;

	int max_path = max(largestUinquePathUtil(node->left, m),
					largestUinquePathUtil(node->right, m));

	// remove current node from path "hash"
	m[node->data]--;

	// if we reached a condition where all duplicate value
	// of current node is deleted
	if (m[node->data] == 0)
		m.erase(node->data);

	return max_path;
}

// A utility function to find long unique value path
int largestUinquePath(Node* node)
{
	if (!node)
		return 0;

	// hash that store all node value
	unordered_map<int, int> hash;

	// return max length unique value path
	return largestUinquePathUtil(node, hash);
}

// Driver program to test above functions
int main()
{
	// Create binary tree shown in above figure
	Node* root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);
	root->right->left = newNode(6);
	root->right->right = newNode(7);
	root->right->left->right = newNode(8);
	root->right->right->right = newNode(9);

	cout << largestUinquePath(root) << endl;

	return 0;
}

输出

时间复杂度 : O (n)

下一个主题哈希 - 用于冲突处理的开放寻址法

← 上一个下一个 →

根到叶子节点路径上不同节点的数量最多

示例

C++ 程序

联系信息

关注我们

教程

面试题

在线编译器

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 选择题

其他

根到叶子节点路径上不同节点的数量最多

示例

C++ 程序

相关帖子

单向链表的归并排序

检测链表中的循环

最长回文子串

循环链表导论和应用

获取二叉树元素的全部后代

在给定数组中具有最大长度最长公共前缀的字符串对

原始数据结构

Recaman 序列

DS 中的垃圾回收

距离之和

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器