搜狐研究院 求二叉树最大叶子节点到最小叶子节点的距离

本文主要是介绍搜狐研究院 求二叉树最大叶子节点到最小叶子节点的距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

先求最大最小叶子节点，再求两节点的LCA（最近公共祖先），求两节点到LCA距离。

import java.util.*;/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}*/
public class Tree {public int getDis(TreeNode root) {// write code hereif(root == null||(root.left == null&&root.right == null))return 0;TreeNode[] tn=new TreeNode[2];int[] max={Integer.MIN_VALUE};int[] min={Integer.MAX_VALUE};findNode(root,tn,max,min);TreeNode maxNode=tn[0];TreeNode minNode=tn[1];if(maxNode == minNode){return 0;}TreeNode lca=LCA(root,maxNode,minNode);int[] count=new int[1];distance(lca,maxNode,0,count);int maxpath=count[0];distance(lca,minNode,0,count);int minpath=count[0];return maxpath+minpath;}//找到最大最小叶节点public void findNode(TreeNode root,TreeNode[] tn,int[] max,int[] min){if(root == null){return;}if(root.left == null&&root.right == null){if(root.val > max[0]){tn[0]=root;max[0]=root.val;}if(root.val < min[0]){tn[1]=root;min[0]=root.val;}return;}findNode(root.left,tn,max,min);findNode(root.right,tn,max,min);}//找到这两个点的LCApublic TreeNode LCA(TreeNode root,TreeNode max,TreeNode min){if(root == null||root == max||root == min){return root;}TreeNode left=LCA(root.left,max,min);TreeNode right=LCA(root.right,max,min);if(left!=null&&right!=null){return root;}if(left!=null){return left;}if(right!=null){return right;}return null;}//分别找到lca和两个点的距离public boolean distance(TreeNode root,TreeNode node,int cur,int[] count){if(root == null||node == null){return false;}if(root == node){count[0]=cur;return true;}cur++;boolean flag=distance(root.left,node,cur,count);if(flag == false){flag=distance(root.right,node,cur,count);}return flag;}
}

这篇关于搜狐研究院 求二叉树最大叶子节点到最小叶子节点的距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---