问题描述:
BST树，又称二叉查找树，求其到所有叶子节点路径的最小值
测试用例一： 10
5 20
返回15；
测试用例二： 100
20 70 110 120
10 null null 89 null null null null
返回130；
程序代码实现：
package examination.written; /**
*
* @author ZhuXY
* @time 2016-6-12 下午9:57:53
*
*/
public class BSTMinLength { public static void main(String[] args) { /*
* root： tNodeRoot
* one layer: tNode21 tNode22
* two layer：tNode11 tNode12 tNode13 tNode14
*/ //构造一个BST树
TreeNode tNode11 = new TreeNode(10, null, null);
TreeNode tNode12 = new TreeNode(50, null, null);
TreeNode tNode13 = new TreeNode(5, null, null);
TreeNode tNode14 = new TreeNode(30, null, null); TreeNode tNode21 = new TreeNode(30, tNode11, tNode12);
TreeNode tNode22 = new TreeNode(30, tNode13, tNode14); TreeNode tNodeRoot = new TreeNode(100, tNode21, tNode22); System.out.println(minlength(tNodeRoot)); } /**
* 获取BST树的最短路径
* @param tNode
* @return minLength：BST最短路径
*/
private static int minlength(TreeNode tNode) {
// TODO Auto-generated method stub
if (tNode != null) {
return getlength(tNode,0);
}
return -1;
} /**
* 递归获取非空根节点到叶子节点的最短路径
* @param tNode
* @param curLength
* @return minLeft>minRight? minRight:minLeft
*/
private static int getlength(TreeNode tNode,int curLength) {
// TODO Auto-generated method stub
int minLeft=-1;
int minRight=-1; // 左子树
if (tNode.leftNode!=null){
minLeft=getlength(tNode.leftNode, curLength+tNode.value);
} // 右子树
if (tNode.rightNode!=null) {
minRight=getlength(tNode.rightNode, curLength+tNode.value);
} // 叶子节点
if (tNode.leftNode==null && tNode.rightNode==null) {
return curLength+tNode.value;
} // 如果左子树为空
if (tNode.leftNode==null) {
return minRight;
} // 如果右子树为空
if (tNode.rightNode==null) {
return minLeft;
} // 如果右子树和左子树都不为空
return minLeft>minRight? minRight:minLeft;
}
} /**
* 定义BST树结构类型
* @author ZhuXY
*
*/
class TreeNode {
int value;
TreeNode leftNode;
TreeNode rightNode; TreeNode(int value, TreeNode lefeNode, TreeNode rightNode) {
this.value = value;
this.leftNode = lefeNode;
this.rightNode = rightNode;
}
}