网易 2016 实习研发工程师 3道 编程题-2

有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。

给定二叉树的根节点root，请返回所求距离。

import java.util.*;

public class Tree {
    
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
        Tree tree = new Tree();  
        TreeNode root = new TreeNode(5);  
        TreeNode left = new TreeNode(4);  
        TreeNode right = new TreeNode(6);  
        root.left = left;  
        root.right = right;  
        TreeNode r2 = new TreeNode(8);  
        right.right = r2;  
        Map<TreeNode, TreeNode> map=new HashMap<>();  
          
        System.out.println(tree.getDis(root));  
          
        //dfs  
        /*tree.dfs(root, map, 1); 
        System.out.println(tree.dpest); 
        for(int i=0;i<tree.leaves.size();i++){ 
            tree.showPath(tree.leaves.get(i),map); 
        }*/  
          
        //bfs  
        //tree.bfs(root);  
    }
    
    private void showPath(TreeNode node,Map<TreeNode, TreeNode> map){  
        while(map.containsKey(node)){  
            System.out.print(node.val+"<--");  
            node = map.get(node);  
        }  
        System.out.println(node.val);  
    }  
    public int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    
    
    public int getDis(TreeNode root) {
        // write code here
        HashMap<Integer, Integer> map = new HashMap<>();  
        helper(root, map);  
        // showMap(map);  
        System.out.println("min:" + min + ",max" + max);  
        // root.left=null;  
        List<Integer> path1 = getPath(min, map, new ArrayList<Integer>());  
        List<Integer> path2 = getPath(max, map, new ArrayList<Integer>());  
  
        int len1 = path1.size();  
        int len2 = path2.size();  
        int result = 0;  
        for (int i = len1 - 1, j = len2 - 1; i >= 0 && j >= 0; i--, j--) {  
            if (path1.get(i) == path2.get(j)) {  
                result = i + j;  
            }  
        }  
        return result;
    }
    
    
    private List<Integer> getPath(int i, Map<Integer, Integer> map, List<Integer> list) {  
        while (map.containsKey(i)) {  
            list.add(i);  
            i = map.get(i);  
        }  
        list.add(i);  
        return list;  
    }
    
    void showMap(Map<Integer, Integer> map) {  
        Iterator<Integer> iterator = map.keySet().iterator();  
        while (iterator.hasNext()) {  
            Integer i = iterator.next();  
            System.out.println("key:" + i + ",value:" + map.get(i));  
        }  
    }  
  
    int dpest = 1;  
    List<TreeNode> leaves=new ArrayList<>();
    
    
    
    public void dfs(TreeNode root, Map<TreeNode, TreeNode> map, int dp) {  
        if (root == null)  
            return;  
        if (root.left == null && root.right == null) {  
            //map.put(root, null);  
            dpest = dpest < dp ? dp : dpest;  
            leaves.add(root);  
        }  
        if (root.left != null) {  
            map.put(root.left, root);  
            dfs(root.left, map, dp + 1);  
        }  
        if (root.right != null) {  
            map.put(root.right, root);  
            dfs(root.right, map, dp + 1);  
        }  
    }  
      
    public void bfs(TreeNode root){  
        LinkedList<TreeNode> queue = new LinkedList<>();  
        queue.add(root);  
        while(!queue.isEmpty()){              
            TreeNode tmp=queue.poll();//queue remove  
            System.out.print(tmp.val+" ");  
            //while()  
            if(tmp.left!=null){  
                queue.add(tmp.left);//queue add  
            }  
            if(tmp.right!=null){  
                queue.add(tmp.right);  
            }  
        }  
    }  
  
    public void helper(TreeNode root, HashMap<Integer, Integer> map) {  
        if (root == null) {  
            return;  
        }  
        if (root.left == null && root.right == null) {  
            int val = root.val;  
            min = val < min ? val : min;  
            max = val > max ? val : max;  
        }  
        if (root.left != null) {  
            map.put(root.left.val, root.val);  
            helper(root.left, map);  
        }  
        if (root.right != null) {  
            map.put(root.right.val, root.val);  
            helper(root.right, map);  
        }  
    }  
    
}

网易 2016 实习研发工程师 3道 编程题-2

原文：http://codeli.blog.51cto.com/4264850/1833651