二叉树的垂直顺序遍历

Question

我尝试按如下方式执行二叉树的垂直顺序遍历：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]}那么我的apProcah出了什么问题呢？

Answer 1

您可以做一个bfs，在左边添加-1，在右边添加1。然后，您可以继续在TreeMap中添加结果，然后在结果中添加所有值。

class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) { return result; }
        Map<Integer, List<Integer>> map = new TreeMap<>();
        helper(root, map);
        result.addAll(map.values());
        return result;
    }
    
    private void helper(TreeNode root, Map<Integer, List<Integer>> map) {
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        q1.offer(root);
        q2.offer(0);
        
        while(!q1.isEmpty()) {
            TreeNode curr = q1.poll();
            int order = q2.poll();
            
            List<Integer> list = map.getOrDefault(order, new ArrayList<>());
            list.add(curr.val);
            map.put(order, list);
            
            if(curr.left != null) {
                q1.offer(curr.left);
                q2.offer(order - 1);
            }
            
            if(curr.right != null) {
                q1.offer(curr.right);
                q2.offer(order + 1);
            }
        }
    }
}