二叉树

//1注意点 权值最大的叶子节点到权值最小的叶子节点,不是所有的节点,自己就因为这个卡了好久
//2.用俩个变量标记俩个节点的位置,求出根节点到他们的路径,如果有重复的路径就减去重复的路径的长度.
class Tree {
    void Inorder(TreeNode *root,vector<int>&v,int &small,int &big){
    //中序遍历获得最小的叶节点和最大的叶节点的索引
        if(!root)
            return;
        Inorder(root->left, v, small, big);
        v.push_back(root->val);
        if(root->left==NULL&&root->right==NULL){//叶子节点
            if(small==-1||big==-1)
                small = big =(int)v.size()-1;
            else{
                if(root->val<v[small]) small = (int)v.size()-1;
                if(root->val>v[big])   big = (int)v.size()-1;
            }
        }
        Inorder(root->right, v, small, big);
    }
public:
    int getDis(TreeNode* root) {
        int small = -1,big = -1;
        vector<int>v;
        Inorder(root, v, small, big);
        TreeNode * p = root;
        vector<int>v1,v2;
        int pos;
        while (true) {//寻找路径
            pos = (int)(find(v.begin(), v.end(),p->val)-v.begin());
            v1.push_back(v[pos]);
            if(small>pos)
                p = p->right;
            else if(small<pos)
                p = p->left;
            else
                break;
        }
        p = root;
        while (true) {
            pos = (int)(find(v.begin(), v.end(),p->val)-v.begin());
            v2.push_back(v[pos]);
            if(big>pos)
                p = p->right;
            else if(big<pos)
                p = p->left;
            else
                break;
        }
        int i,j;
        for (i=0,j=0;j<v2.size()-1&&i<v1.size()-1; ++i,++j) {//去重
            if(!(v1[i]==v2[j]&&v1[i+1]==v2[j+1]))
                break;
        }
        return (int)v1.size()-1+(int)v2.size()-1-2*i;
    }
};

	class Tree{
public:
	int min_key = INT_MAX;
	int min_level;
	int max_level;
	int max_key = INT_MIN;
	void find_min_max(TreeNode* root, int level)
	{
		if (root == NULL)return;
		if (!root->left && !root->right && root->val < min_key)
		{
			min_key = root->val;
			min_level = level;
		}
		if (!root->left && !root->right && root->val > max_key)
		{
			max_key = root->val;
			max_level = level;
		}
		find_min_max(root->left, level + 1);
		find_min_max(root->right, level + 1);
	}

	int find_level(TreeNode* root, int key)
	{
		if (root == NULL)return -1;
		if (key == root->val)return 0;
		int level = find_level(root->left, key);
		if (level == -1)
			level = find_level(root->right, key);
		if (level != -1)
			return level + 1;
		return -1;
	}
	TreeNode* find_father(TreeNode* root, int key1, int key2)
	{
		if (root == NULL || key1 == root->val || key2 == root->val)
			return root;
		TreeNode* left = find_father(root->left, key1, key2);
		TreeNode* right = find_father(root->right, key1, key2);
		if (left && right)return root;
		return left ? left : right;
	}

	int getDis(TreeNode* root) {
		find_min_max(root, 0);
		TreeNode* father = find_father(root, min_key, max_key);
		int father_level = find_level(root, father->val);
		return min_level + max_level - 2 * father_level;
	}
};

int getDis(TreeNode* root) {
        // write code here
        map<int, pair<int,int>>parent;//不同权值对应的父亲（权值和编号）
        queue<TreeNode*>que;//辅助队列，按层遍历找父节点
        que.push(root);
        int max = -1000;//最大权值
        int min = 1000;//最小权值
        parent[root->val]=make_pair(0,0);//根节点的父节点
        int cnt = 0;//起始编号
        while (!que.empty()){
            TreeNode*temp = que.front();//队首元素
            cnt++;
            if (temp->left){
                parent[(temp->left)->val]=make_pair(temp->val,cnt);
                que.push(temp->left);
            }
            if (temp->right){
                parent[(temp->right)->val]=make_pair(temp->val,cnt);
                que.push(temp->right);
            }
            if (temp->left == NULL&&temp->right == NULL){//如果是子节点
                if ((temp->val)>max){
                    max = temp->val;
                } 
                if ((temp->val)<min){
                    min = temp->val;
                }
            }
            que.pop();
        }
        int result1 = 0;
        int result2 = 0;
        while(max!=min){
            if(parent[max].second>parent[min].second){
                max=parent[max].first;
                result1++;
            }
            else if(parent[min].second>parent[max].second){
                min=parent[min].first;
                result2++;
            }
            else{
               max=parent[max].first;
               min=parent[min].first;
               result2++;
               result1++;
            }
        }
        return result1 + result2;
    }

宽度优先遍历+深度优先遍历

import java.util.*;

public class Tree {
    public int getDis(TreeNode root) {
        // 层次遍历找到最值叶节点
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode minNode = root;
        TreeNode maxNode = root;
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur.left == null && cur.right == null){
                if(cur.val > maxNode.val){
                    maxNode = cur;
                }else if(cur.val < minNode.val){
                    minNode = cur;
                }
            }
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        // 寻找最值节点的最近公共祖先
        TreeNode lcaNode = lowestCommonAncestor(root, minNode, maxNode);
        // 计算距离
        return disBetweenNode(lcaNode, minNode) + disBetweenNode(lcaNode, maxNode);
    }
    
    // 层次遍历计算距离
    private int disBetweenNode(TreeNode node1, TreeNode node2) {
        int dis = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node1);
        while(!queue.isEmpty()){
            int queueSize = queue.size();
            for(int i = 0; i < queueSize; i++){
                TreeNode cur = queue.poll();
                if(cur == node2){
                    return dis;
                }
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
            }
            dis++;
        }
        return dis;
    }
    
    private TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }
}

 # -*- coding:utf-8 -*-

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
'''
最高赞的python版
'''
class Tree:
    ma = 0
    macode = ''
    mi = 9999
    micode = ''
    def getDis(self, root):
        # write code here
        if not root:
            return 0
        def getCode(root,code,codec):
            if root:
                codec += code
                if root.left == None and root.right == None:
                    if root.val > self.ma:
                        self.ma = root.val
                        self.macode = codec
                    if root.val < self.mi:
                        self.mi = root.val
                        self.micode = codec
                getCode(root.left,'0',codec)
                #codec.pop()
                getCode(root.right,'1',codec)
        getCode(root,'-1','')
        #print macode,micode
        lma = len(self.macode)
        lmi = len(self.micode)
        #return lma
        i = 0
        while i < min(lma,lmi):
            if self.macode[i] != self.micode[i]:
                r = lma-i+lmi-i
            	return r
            i += 1

import java.util.*;
public class Tree {
	public int max_node_value = -1;
	public int min_node_value = -1;
	public LinkedList<Integer> road = new LinkedList<Integer>();
	public LinkedList<Integer> min_road = new LinkedList<Integer>();
	public LinkedList<Integer> max_road = new LinkedList<Integer>();
	public int getDis(TreeNode root) {
		road.addLast(root.val);
		dfs(root);
		while (max_road.getFirst() == min_road.getFirst()) {
			max_road.removeFirst();
			min_road.removeFirst();
		}
		return max_road.si敏感词_road.size();
	}

	public void dfs(TreeNode node) {
		if (node.left == null && node.right == null) {
			if (max_node_value == -1) {
				max_node_value = node.val;
				max_road = (LinkedList<Integer>) road.clone();
			} else if (max_node_value < node.val) {
				max_node_value = node.val;
				max_road = (LinkedList<Integer>) road.clone();
			}
			if (min_node_value == -1) {
				min_node_value = node.val;
				min_road = (LinkedList<Integer>) road.clone();
			} else if (min_node_value > node.val) {
				min_node_value = node.val;
				min_road = (LinkedList<Integer>) road.clone();
			}
			return;
		}
		if (node.left != null) {
			road.addLast(node.left.val);
			dfs(node.left);
			road.removeLast();
		}
		if (node.right != null) {
			road.addLast(node.right.val);
			dfs(node.right);
			road.removeLast();
		}
	}
}

//后续遍历树，并打印从根节点到叶子节点的路径

class Tree {
public:
    int getDis(TreeNode* root) {
        if(!root)
            return 0;
        vector<TreeNode*> vec,max,min;
        TreeNode* p=root,*q;
        do{
        	while(p){
        		vec.push_back(p);
				p=p->left; 
			}
			q=NULL;
			while(!vec.empty()){
				p=vec.back();
				vec.pop_back();
				if(p->right==q){
					q=p;
					if(!p->left&&!p->right){
						vec.push_back(p);
						if(max.size()==0||max.back()->val<vec.back()->val)
                			max=vec;
                		if(min.size()==0||min.back()->val>vec.back()->val)
                			min=vec;
						vec.pop_back();					
					}		
				}else{
					vec.push_back(p);								
					p=p->right;
					break;
				}
			}	
		}while(!vec.empty());
        int i;
        for(i=0;i<max.size()&&i<min.size()&&max[i]==min[i];i++);
        return max.size()-2*i+min.size();
    }
};

//这个题关键是找到最大结点和最小结点刚开始分叉的地方，也就是共有路径的结束点。那么最后的距离就等于（最大结点的路径长度-共有路径长度）+（最小结点的路径长度-共有路径长度）
//可以采取哈夫曼编码树的方法，记录从根结点到该结点的唯一路径。如：0101
//题目说权值各不相同，所以可以用权值作为该结点的唯一ID；
//以上就是我们需要记录的信息，有两个，结点ID（权值）和到该结点的路径。
//对于路径的存储，我们采用一个队列来存储，遍历时每往树的下层走一步，就在队列里加0（左子树）或1（右子树）
//所以我们采取深度优先遍历DFS，并且遍历完成后记录每个结点的ID和路径信息。函数UpdateWhileDFS
//信息保存在一个MAP里，MAP的结构为<权值，路径>，这样根据结点权值，就可以取出到该结点的路径。




class Tree{
private:
	int max = -999999;
	int min = 999999;
//存储信息的MAP，MAP的结构为<权值，路径> unordered_map<int, queue<int>> info;

public:
	void UpdateWhileDFS(TreeNode* root, queue<int> path,int mark){
//mark为哈夫曼编码，取0或1.左子树为0，右子树为1.根节点为NULL
//更新结点路径
		path.push(mark);
//存储结点路径
		info[root->value] = path;
//更新最大值
		if (root->value > max)
			max = root->value;
//更新最小值
		if (root->value < min)
			min = root->value;
//递归遍历左子树
		if (root->left != NULL)
//左子树的哈夫曼编码是0，所以告诉函数你应该在路径的最后加0
			UpdateWhileDFS(root->left, path,0);
		if (root->right != NULL) //右子树的哈夫曼编码是0，所以告诉函数你应该在路径的最后加1。 

UpdateWhileDFS(root->right, path, 1); }
	int getDis(TreeNode * root){	
//队列用于存储路径	
		queue<int> q;
//初始化根结点的路径队
		info[root->value] = q;
//遍历，并更新路径信息。
		UpdateWhileDFS(root, info[root->value],NULL);
//取出最大结点的路径
		queue<int> maxQueue = info[max];
//取出最小结点的路径
		queue<int> minQueue = info[min];
//利用循环去掉共有路径
		while (!maxQueue.empty()&& !minQueue.empty())
		{
			if (maxQueue.front()!=minQueue.front())
				break;
			maxQueue.pop();
			minQueue.pop();
		}
//循环结束，说明此时到达分叉点
		return maxQueue.si敏感词Queue.size();

	}

};

class Tree:
    def getDis(self, root):
        # 层次遍历 O(N)
        max_leaf, min_leaf, parents = self.level_triversal(root)
        
        # 构造出从权值最大/最小的叶子结点到根节点的路径 2*O(lg(N))
        max_leaf_to_root = self.construct_path(max_leaf, root.val, parents)
        min_leaf_to_root = self.construct_path(min_leaf, root.val, parents)
        
        # 路径上的公共父结点，至少包含一个root结点
        com_nodes = list(set(max_leaf_to_root).intersection(
        set(min_leaf_to_root)))
        
        # 计算距离
        dis = (len(max_leaf_to_root) - 1) + (len(min_leaf_to_root) - 1)
        if len(com_nodes) > 1:
            # 此时需要去掉重复边
            dis -= len(com_nodes)
        return dis
            
    def level_triversal(self, root):
        """
        层次遍历，并记录权值最大的叶子结点max_leaf、
        权值最小的叶子结点min_leaf、父子关系parents
        """
        queue = []
        queue.append(root)
        parents = {}
        parents[root.val] = None
        max_leaf = None
        min_leaf = None
        
        while len(queue) > 0:
            
            cur = queue.pop(0)
            
            if cur.left is None and cur.right is None:
                if max_leaf is None or max_leaf < cur.val:
                    max_leaf = cur.val
                if min_leaf is None or cur.val < min_leaf:
                    min_leaf = cur.val
            
            if cur.left is not None:
                queue.append(cur.left)
                parents[cur.left.val] = cur.val
                
            if cur.right is not None:
                queue.append(cur.right)
                parents[cur.right.val] = cur.val
                
        return (max_leaf, min_leaf, parents)

    def construct_path(self, begin, end, parents):
        """
        根据父子关系构造出从begin到end的路径
        """
        cur = begin
        queue = []
        while cur != end:
            queue.append(cur)
            cur = parents[cur]
        queue.append(cur)
        return queue

//典型的二进制编码题，算出叶子节点二进制编码，再比编码，计算后缀长度和
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
    }

	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;



	}

//受大神们的启发，找路径，然后去重，代码较短。时间复杂度应该就是遍历二叉树的复杂度。
class Tree {
public:
    void getCode(map<int, string>&m, TreeNode*root,string s) {
		if (root->left == NULL && root->right == NULL) {
			m[root->val] = s;      //记录每一个叶子的权值和编码
			return;
		}
		if (root->left) {
			getCode(m, root->left, (s + '1'));
		}
		if (root->right) {
			getCode(m, root->right, (s + '0'));
		}
	}
	int getDis(TreeNode* root) {
		// write code here
		map<int, string>m;//<权值，编码>
		string s;
		getCode(m, root,s);
		auto it = m.begin();
		string s1 = it->second;
		auto end = (--m.end());
		string s2 = end->second;
		int i = 0, j = 0;
		for (; i < s1.size() && j < s2.size()&&s1[i] == s2[j]; i++, j++) {}
		return s1.size() - i + s2.size() - j;
	}
};

class Tree {
public:
	vector<int> min_path;
	vector<int> max_path;
	int mmin;
	int mmax;

    int getDis(TreeNode* root) {
    	mmin = numeric_limits<int>::max();
    	mmax = numeric_limits<int>::min();
    	vector<int> vec;
        dfs(root,vec);
        if(min_path.size() == 0) return 0;
        for(int i =0;;i++)
        {
        	if(min_path[i] == max_path[i])
        		continue;
        	else {
        		return min_path.size() - i + max_path.size() - i;
        	}
        }
    }

    void dfs(TreeNode* root,vector<int> &vec)
    {
    	if(root == NULL) return ;
    	if((root->left == NULL) && (root->right == NULL))
    	{
    		if(root->val < mmin)
    		{
    			mmin = root->val;
    			min_path.assign(vec.begin(),vec.end());
    		}
    		if(root->val > mmax)
    		{
    			mmax = root->val;
    			max_path.assign(vec.begin(),vec.end());
    		}

    	}
    	vec.push_back(-1);
    	dfs(root->left,vec);
    	vec.pop_back();

    	vec.push_back(1);
    	dfs(root->right,vec);
    	vec.pop_back();
    }
};

首先深度遍历所有的叶子节点，在遍历的同时记录叶子节点的路径。记录下最小的叶子节点路径。
因为所有的路径都是从根节点出发的，所以-1表示向左，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 {
    public int getDis(TreeNode root) {
        // write code here
        // 妈呀，这也太难了吧
        // 我需要做的是，从一个角落开始给每一个节点编号，中序遍历是可以的。但很麻烦，想不到
        if(root==null) return -1;
        else if(root.left==root.right&&root.left==null) return 0;
        Map<Integer,Integer> record = new HashMap<>();
        Map<Integer,Integer> father = new HashMap<>();
        //用这个记录每个权值对应的dis
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        // 我可以将根节点的depth设置为0，左子树的深度按照正的增加，右子树的深度按照负的增加
        // record.put(root.val,0);//root肯定不是叶节点了
        //然后我还是可以按照广度优先
        ArrayList<TreeNode> nodes = new ArrayList<>();
        if(root.left!=null){
            nodes.add(root.left);
            record.put(root.left.val,1);
            father.put(root.left.val,root.val);
        }
        if(root.right!=null){
            nodes.add(root.right);
            record.put(root.right.val,-1);
            father.put(root.right.val,root.val);
        }
        int index = 0 ;
        while(index<nodes.size()){//我真的觉得自己没做错啊。这个确实没错，但这是所有节点啊啊啊啊啊啊
            TreeNode node = nodes.get(index);
            if(node.left==null&&node.right==null){
                if(node.val>max) max=node.val;
                if(node.val<min) min=node.val;
                index++;
                continue;
            }
            int thisdepth = record.get(node.val);
            thisdepth=thisdepth>0?thisdepth+1:thisdepth-1;
            if(node.left!=null){
                nodes.add(node.left);
                record.put(node.left.val,thisdepth);
                father.put(node.left.val,node.val);
            }
            if(node.right!=null){
                nodes.add(node.right);
                record.put(node.right.val,thisdepth);
                father.put(node.right.val,node.val);
            }
            index++;
        }
        //要考虑的问题还有哦，如果max和min同在左子树或者右子树呢？
        //那你还得找到他们第一个共同祖先？好像又麻烦了哦，那就再加一个Map吗？用空间换时间，那会不会，超出啊
        if(record.get(min)*record.get(max)<0)
            return Math.abs(record.get(min)-record.get(max));
        else{
            //找共同的祖先活动开始，吓死我了，没有超过空间限制。
            int father1 = father.get(min);
            int father2 = father.get(max);
            while(father1!=father2){
                father1 = father.get(father1);
                father2 = father.get(father2);
            }
            int father_depth = record.get(father1);
            return Math.abs(2*father_depth-record.get(min)-record.get(max));
        }
    }
}

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');
    }
}