java二叉树的垂直顺序遍历
我正在尝试执行二叉树的垂直顺序遍历,如下所示: 1) 找出每个节点与根节点之间的最小和最大水平距离 2) 创建将水平距离映射到相应节点的hashmap(Map>;)
然而,我得到了不想要的输出,我认为在实现中有一些错误,因为算法对我来说似乎是正确的
以下是完整的代码:
import java.util.*;
class Node{
int data;
Node right;
Node left;
Node(int data){
this.data = data;
}
}
class Min_Max{
int min;
int max;
Min_Max(int min, int max){
this.min=min;
this.max=max;
}
}
class VerticalOrderTraversalUsingHashing{
public static void findMinMax(Node root,Min_Max obj, int hd){
if(root==null)
return;
if(hd > obj.max)
obj.max = hd;
else if(hd < obj.min)
obj.min = hd;
findMinMax(root.left, obj, hd-1);
findMinMax(root.right, obj, hd+1);
}
public static void verticalOrderTraversal(Node root, Map<Integer,Vector<Integer>> map,int hd){
if(root == null)
return;
if(map.get(hd)==null){
Vector<Integer> temp = new Vector<>();
temp.add(root.data);
map.put(hd,temp);
} else {
Vector<Integer> temp = map.get(hd);
temp.add(root.data);
map.put(hd,temp);
}
}
public static void main(String [] args){
Node root = new Node(12);
root.left = new Node(6);
root.right = new Node(19);
root.left.right = new Node(8);
root.left.left = new Node(-23);
root.right.left = new Node(18);
root.right.right = new Node(52);
Min_Max obj = new Min_Max(99999, -99999);
findMinMax(root, obj, 0);
Map<Integer,Vector<Integer>> map = new HashMap<>();
for(int i=obj.min;i<=obj.max;i++){
Vector <Integer> v = new Vector<>();
v.add(99999);//dummy node to initialize the map
map.put(i,v);
}
verticalOrderTraversal(root, map, 0);
Set keys = map.keySet();
Iterator itr=keys.iterator();
System.out.println(map);
}
}
输出:{-1=[99999],0=[99999,12],-2=[99999],1=[99999],2=[99999]} 那么我的方法有什么问题
# 1 楼答案
你可以做一个bfs,在左边加
-1
,在右边加+1
。 然后可以继续在树形图中添加结果,然后将所有值添加到结果中