当前位置：首页 > news >正文

算法面试题-- 连接树的所有兄弟节点

news 来源：原创 2024/5/6 14:47:14

前几天遇到了一个面试题，考察的也是树，和普通的树遍历不同，稍微改动了一下，就是对已经建立好的树，每个连接兄弟节点。
节点定义如下：
public IList<Node> Children;
public Node Right;
public string Val;
包含了子节点集合，右节点。
问题：现在树已经建立好，可是Right为空，把所有的兄弟节点（不是同一个Parent的也要连）连接起来。

树：

连接后变成：

思路：

1. 遍历每个子节点，连接当前子节点的下1个子节点（除最后一个）
2. 遍历每个子节点时，将当前子节点的最后一个子节点与下1个子节点的第一个子节点连接（如果存在）
3. 递归执行

实现如下：

void Main()
{
	// setup 
	var root = new Node("R");
	var childGroup1 = new List<Node>();
	root.Children.Add(new Node("A1", new List<Node>(){new Node("B1"),new Node("B2")}));
	root.Children.Add(new Node("A2", new List<Node>(){new Node("B3"),new Node("B4")}));
	
	// search and link the brother nodes
	TravelAndLink(root);
	
	Console.WriteLine(root);
}


static void TravelAndLink(Node current){
	if(current == null || current.Children == null){
		return;
	}
	
	var len = current.Children.Count;
	for(var i = 0;i < len; i++){
		// link right if have 
		if(i < len - 1){
			current.Children[i].Right = current.Children[i+1];
			
			// link current son's last son to his next brother's first son if possible
			if(current.Children[i].Children.Any() && current.Children[i+1].Children.Any()){
				var c1 = current.Children[i].Children.Last();
				var c2 = current.Children[i+1].Children.First();
				c1.Right = c2;
			}
		}
		
		//recursive
		TravelAndLink(current.Children[i]);
	}
	
	// link my last child to brother's first child if impossible
}


public class Node
	{
		public Node(string v, IEnumerable<Node> children = null)
		{
			Val = v;
			
			Children = new List<Node>();
			if(children != null){
				Children = children.ToArray();
			}
			
			Right = null;
		}
	
	    public IList<Node> Children;
	    public Node Right;
		public string Val; 
	}