二叉树

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 here
        fun(root,"0");
        char[] minchars=minstr.toCharArray();
        char[] maxchars=maxstr.toCharArray();
        int i;
        for(i=0;i<minchars.length&&i<maxchars.length;i++)
            if(minchars[i]!=maxchars[i])
                break;
        return minchars.length+maxchars.length-i*2;
    }
    
    int min=Integer.MAX_VALUE;
    int max=0;
    String minstr;
    String maxstr;
    void fun(TreeNode node,String str)
    {
        if(node==null)
            return;
        if(node.left==null&&node.right==null)
        {
            if(min>node.val)
            {
                min=node.val;
                minstr=str;
            }
            if(max<node.val)
            {
                max=node.val;
                maxstr=str;
            }
        }
        fun(node.left,str+'0');
        fun(node.right,str+'1');
    }
}

	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 {



	private TreeNode maxNode = new TreeNode(Integer.MIN_VALUE);



	private TreeNode minNode = new TreeNode(Integer.MAX_VALUE);



	



	public int getDis(TreeNode root) {



	    // write code here



	    getMaxMin(root);//找到最大最小叶子节点



	    TreeNode lcaNode = getLCA(root);//找LCA



	    int a = getNodeDis(lcaNode, maxNode);//最大值叶子节点到LCA的距离；



	    int b = getNodeDis(lcaNode, minNode);//最小值叶子节点到LCA的距离；



	    return a+b;



	}



	



	// 先找到最大最小叶子节点



	public void getMaxMin(TreeNode root) {



	    if (root == null) {



	        return;



	    }



	    if (root.left == null && root.right == null) {



	        if (root.val > maxNode.val) {



	            maxNode = root;



	        } else if (root.val < minNode.val) {



	            minNode = root;



	        }



	    }



	    getMaxMin(root.left);



	    getMaxMin(root.right);



	}



	



	// LCA最近公共祖先



	public TreeNode getLCA(TreeNode root) {



	    if (root == null) {// 说明是空树



	        return null;



	    }



	    if (root.val == maxNode.val || root.val == minNode.val) {// 在当前树的根节点上找到两个节点之一



	        return root;



	    }



	    TreeNode leftNode = getLCA(root.left);// 左子树中的查找两个节点并返回查找结果



	    TreeNode rightNode = getLCA(root.right);// 右子树中查找两个节点并返回查找结果



	    if (leftNode == null) {// 左子树中没找到，则一定在右子树上



	        return rightNode;



	    } else if (rightNode == null) {// 右子树没找到一定在左子树上



	        return leftNode;



	    } else {// 左右子树均找到一个节点，则根节点为最近公共祖先



	        return root;



	    }



	}



	



	//获取叶子节点到LCA距离



	public int getNodeDis(TreeNode lcaNode, TreeNode node){



	    if(lcaNode==null){



	        return -1;



	    }



	    if(lcaNode.val==node.val){



	         return 0;



	    }



	    //三种情况：两个均在左子树；两个均在右子树；一左一右，所以不能用if-elseif结构



	    int distance = getNodeDis(lcaNode.left, node);//左子树未找到两个节点之一



	    if(distance==-1){



	        distance = getNodeDis(lcaNode.right, node);



	    }



	    if(distance!=-1){



	        return distance+1;



	    }



	



	    return -1;



	}

//典型的二进制编码题，算出叶子节点二进制编码，再比编码，计算后缀长度和
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 {
    private int max=0;
	private int min=99999;
	private StringBuilder maxcodec;
	private StringBuilder mincodec;
    	void PreOrder(TreeNode T,char code,StringBuilder codec){
		if(T!=null){			
			codec.append(code);
			if(T.left==null && T.right==null)
			{
				if(max<T.val)
				{
					max=T.val;
					maxcodec = codec;
				}
				
				if(min>T.val)
				{
					min=T.val;
					mincodec = codec;
				}
			}
			PreOrder(T.left,'0',new StringBuilder(codec));
			PreOrder(T.right,'1',new StringBuilder(codec));
		}
	}
    public int getDis(TreeNode root) {
        PreOrder(root,'0',new StringBuilder());
    	int index=0;
    	for(index=0; index<(maxcodec.length()>mincodec.length()?maxcodec.length():mincodec.length());index++)
    	{
    		if(maxcodec.charAt(index)!=mincodec.charAt(index))
    			break;
    	}
		return (maxcodec.substring(index).length()+mincodec.substring(index).length());
    
        // write code here
    }