关于树的一些算法

桃扇骨 2022-08-11 16:36 167阅读 0赞

阿里笔试，第二题，在一棵树中找出两个节点，他们的最大值的绝对值是最大的，当时题目没看清楚，以为是编程之美原题，直接把前两天OJ的代码附上。

现给出源代码：

#include<iostream>
    using namespace std;
    int max = -10000;
    int min = 10000;
    struct Node
    {
    	int value;
    	Node *pleft;
    	Node *pright;
    };
    Node *CreateTree()//先序遍历初始化二叉树
    {
    	int v = 0;
    	Node *t = NULL;
    	if(scanf("%d",&v) == EOF)//EOF即输入ctrl+z时的值，
    		t = NULL;
    	else
    	{
    		t = (Node *)malloc(sizeof(Node));
    		t->value = v;
    		t->pleft = CreateTree();
    		t->pright = CreateTree();
    	}
    	return t;
    }
    void SearchMaxValue(Node *head)//中序遍历寻找最大值
    {
    	if(head == NULL)
    		return;
    	SearchMaxValue(head->pleft);
    	cout<<head->value<<endl;
    	if(head->value > max)
    		max = head->value;
    	if(head->value < min)
    		min = head->value;	
    	SearchMaxValue(head->pright);
    	return;
    }
    int main()
    {
    	Node *head = CreateTree();
    	SearchMaxValue(head);//找出最大差值
    	cout<<max - min<<endl;
    	return 0;
    }

如果用非递归来编译树代码如下：

void NoRecursion_SearchMaxValue(Node *head)
    {
    	stack<Node *> sk;
    	Node *p = head;
    	while(p != NULL || !sk.empty())//p有节点，而且有值
    	{
    		while(p != NULL)
    		{
    			sk.push(p);
    			p = p->pleft;
    		}
    		if(!sk.empty())
    		{
    			p = sk.top();
    			cout<<p->value<<" ";
    			if(p->value > max)
    				max = p->value;
    			if(p->value < min)
    				min = p->value;
    			sk.pop();
    			p = p->pright;
    		}
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，167人围观）

还没有评论，来说两句吧...

相关阅读

相关关于排名算法的一些思考引用

最近开始在简书上混，今日在首页上不经意间看到一篇《[从豆瓣电影评分算法说起][Link 1]》，感觉有点眼熟，就点了进去。其实阿北的那篇《豆瓣电影评分八问》，我也是刚看过，

叁歲伎倆/ 2022年12月31日 05:28/ 0 赞/ 193 阅读

相关关于“树”的算法：现实生活中的决策树

> 全文共2874字，预计学习时长8分钟 ![880a02b74d04ddca189664b6aba1a54a.png][] 图源：unsplash 就像树木是人类生活的

拼搏现实的明天。/ 2022年12月23日 11:12/ 0 赞/ 151 阅读

相关关于二叉树的一些基本操作，C++

include <iostream> include <cassert> include <queue> using namespac

骑猪看日落/ 2022年12月12日 15:02/ 0 赞/ 195 阅读

相关关于树的一些算法

阿里笔试，第二题，在一棵树中找出两个节点，他们的最大值的绝对值是最大的，当时题目没看清楚，以为是编程之美原题，直接把前两天OJ的代码附上。现给出源代码： incl

桃扇骨/ 2022年08月11日 16:36/ 0 赞/ 168 阅读

相关 [转]关于寻路算法的一些思考

关于寻路算法的一些思考（1）：A\算法介绍物体的移动算法似乎显得很简单，然而寻路规划问题却十分复杂。考虑下面这个例子： ![7cc829

川长思鸟来/ 2022年07月15日 15:57/ 0 赞/ 289 阅读

相关关于数据结构中一些二叉树的定义

1、满二叉树定义：除最后一层的结点外，每一层的所有结点都有两个子结点。另外一个定义：深度为k且有2^k-1个结点的二叉树。满二叉树是一颗树深度为h，

悠悠/ 2022年06月11日 07:36/ 0 赞/ 331 阅读

相关关于Promise的一些

[github同步][github] 1.定义 > The Promise object represents the eventual completion (or

矫情吗；*/ 2022年05月31日 14:10/ 0 赞/ 274 阅读

相关关于树的一些题

判断题 -------------------- 1. 任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。 `T` --------------------

左手的ㄟ右手/ 2022年01月27日 23:05/ 0 赞/ 381 阅读

相关关于二叉树的一些问题

1，写一个算法，要求给定一个二叉树，算法能够返回其高度？解答：可以递归地去求子树的高度，这个问题的子问题就是，以当前节点为根的树德高度，为其左右子树高度的最大者再

朱雀/ 2021年11月19日 14:44/ 0 赞/ 342 阅读

相关关于二叉检索树（BST）的一些问题

1，给定一个BST，其中的节点出了key和左右孩子指针left,right之外，还有另一个指针neighbour，当前BST中所有节点的neighbour指针全部为空

比眉伴天荒/ 2021年11月17日 12:48/ 0 赞/ 247 阅读