网易有道笔试:
(1).
求一个二叉树中任意两个节点间的距离,
两个节点的距离的定义是 这两个节点间边的个数,
比如某个孩子节点和父节点间的距离是1,和相邻兄弟节点间的距离是2,优化时间空间复杂度。
C# codes as below:
using System;
namespace ConsoleApp
{
class RunClass
{
static void Main()
{
Node<int> i1 = new Node<int>() { Value = 4 };
Node<int> i2 = new Node<int>() { Value = 8 };
Node<int> i3 = new Node<int>() { Value = 12 };
Node<int> i4 = new Node<int>() { Value = 16 };
Node<int> i5 = new Node<int>() { Value = 6, Left = i1, Right = i2 };
Node<int> i6 = new Node<int>() { Value = 14, Left = i3, Right = i4 };
Node<int> i7 = new Node<int>() { Value = 10, Left = i5, Right = i6 };
Tree<int> tree = new Tree<int>() { Root = i7 };
int distance = new Helper().GetDistance<int>(tree, i4, i1);
Console.WriteLine(distance);
Console.ReadLine();
}
}
class Helper
{
public int GetDistance<T>(Tree<T> tree, Node<T> node1, Node<T> node2)
{
int length = (int)Math.Pow(2, CountMaxDepth<T>(tree) + 1) - 1;
Node<T>[] nodes = new Node<T>[length];
Node<T> root = tree.Root;
AddNodes<T>(nodes, root);
int index1 = FindNode<T>(nodes, node1);
int index2 = FindNode<T>(nodes, node2);
return CountDistance(index1, index2);
}
public int CountDistance(int i, int j)
{
if (i < j)
{
int k = i;
i = j;
j = k;
}
int distance = 0;
if (i != j)
{
distance += 1;
if (i % 2 == 1)
i = (i - 1) / 2;
else
i = i / 2 - 1;
distance += CountDistance(i, j);
}
return distance;
}
public int FindNode<T>(Node<T>[] nodes, Node<T> node)
{
for (int i = 0; i < nodes.Length; i++)
{
if (object.ReferenceEquals(nodes[i], node))
return i;
}
return -1;
}
private void AddNodes<T>(Node<T>[] nodes, Node<T> node, int currentIndex = 0)
{
nodes[currentIndex] = node;
if (node.Left != null)
{
AddNodes<T>(nodes, node.Left, 2 * currentIndex + 1);
}
if (node.Right != null)
{
AddNodes<T>(nodes, node.Right, 2 * currentIndex + 2);
}
}
public int CountMaxDepth<T>(Tree<T> tree)
{
if (tree == null||tree.Root==null)
return 0;
Node<T> root = tree.Root;
if (root.Left == null && root.Right == null)
return 0;
Tree<T> leftTree = new Tree<T>() { Root = root.Left };
Tree<T> rightTree = new Tree<T>() { Root = root.Right };
int leftMaxLevel = CountMaxDepth<T>(leftTree);
int rightMaxLevel = CountMaxDepth<T>(rightTree);
return leftMaxLevel > rightMaxLevel ? leftMaxLevel + 1 : rightMaxLevel + 1;
}
}
class Tree<T>
{
public Node<T> Root { get; set; }
}
class Node<T>
{
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
public T Value { get; set; }
}
}
分享到:
相关推荐
求二叉树中节点的最大距离
求二叉树中任意两个节点的最大距离,。。用C++在VC下实现
二叉树的直径指的是该二叉树上任意两个节点路径长度中最长的一条,其长度为这两个节点之间经过的边数。 可以使用深度优先搜索(DFS)来求解二叉树的直径。具体做法如下: 定义一个私有变量 diameter,用于存储当前...
C语言 二叉树 C 数据结构 用C语言实现建立一棵二叉树 支持插入,删除结点,画出二叉树
二叉树的直径,二叉树的直径指的是二叉树中任意两个节点间最长路径的长度。路径可以经过任意节点,但是不能重复经过同一个节点。求二叉树直径的思路。递归。
按照某种遍历次序对二叉树进行遍历,可以把二叉树中所有结点排成一个线性序列。在集体应用中,有时需要访问二叉树中的结点在某种遍历序列中前驱和后继,此时,在存储结构中应该保存结点在某种遍历序列中的前驱和后继...
本程序包括二叉树的一些常见的相关操作,比如非递归建立二叉树,二叉树的非递归遍历,非递归求二叉树的叶子数目,层数,任意两个节点的公共祖先,跟到叶子节点的所有路径,根据中序和后序的遍历结果建立二叉树等等。
二叉树是n(n≥0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 特点:⑴ 每个结点最多有两棵子树; ⑵ 二叉树是...
平衡二叉树(AVL树):平衡二叉树是一种特殊的二叉搜索树,它要求任何节点的两个子树的高度差不超过1。平衡二叉树的插入和删除操作都需要进行旋转操作来维持平衡状态,从而保证查找操作的时间复杂度为O(log n)。 ...
一棵二叉树的直径长度是任意两个结点路径长度中的最大值。 这条路径可能穿过也可能不穿过根结点。 答案为3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 输入格式 共n行。 第一行一个整数n,表示有n个结点,编号为1...
给定一个二叉搜索树的根节点 root,返回树中任意两节点的差的最小值。 示例: 输入: root = [4,2,6,1,3,null,null] 输出: 1 解释: 注意,root是树节点对象(TreeNode object),而不是数组。 给定的树 [4,2,6,1,3,null...
直径或宽度(树中任意两个节点之间的最长距离) 二叉树节点的组成部分 它保存的数据类型,例如Int或String等 指向左子节点的指针 指向右子节点的指针 常见操作 遍历 插入 删除 二叉树节点 class BinaryTreeNode <...
对二叉树,计算任意两个结点的最短路径长度。 输入 第一行输入测试数据组数T 第二行输入n,m 。n代表结点的个数,m代表要查询的数据组数 接下来n行,每行输入两个数,代表1~n结点的孩子结点,如果没有孩子结点则输入-...
单链表交换任意两个元素(不包括表头) 8.判断单链表是否有环?如何找到环的“起始”点?如何知道环的长度? 9.判断两个单链表是否相交 10.两个单链表相交,计算相交点 11.用链表模拟大整数加法运算 12.单链表...
红黑书:红黑树是在普通二叉树上,对每个节点添加一个颜色属性形成的,需要 同时满足一下五条性质 (1)节点是红色或者是黑色; (2)根节点是黑色; (3)每个叶节点(NIL 或空节点)是黑色; (4)每个红色节点的...
一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意:两结点之间的路径长度是...
如何求二叉树的任意两个节点的公共祖先,可以通过编译
连通图是指图中任意两个顶点之间14.能进行二分查找的线性表,必须以16.下面的说法中正确的是 (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。 (2)按二叉树定义,具有三个节点的二叉树共有6种。17.以下与...
二叉树:每个节点最多含有两个子树的树称为二叉树 二叉树的性质 在二叉树的第i层上至多有2^(i-1)个结点(i>0) 深度为k的二叉树至多有2^k-1个结点(k>0) 对于任意一棵二叉树,如果其叶结点为N0,而度数为2的结点...
一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意:两结点之间的路径长度是...