有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。
给定二叉树的根节点root，请返回所求距离。
[编程题]二叉树
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表示向右。那么记录下最小叶子的路径，和最大叶子的路径。 然后比较一下他们相同的前缀，剩下的值相加就是最后的答案
发表于 2016-04-13 21:04:48
回复(0)
//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;
}
};
发表于 2016-03-27 17:59:14
回复(1)
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; } };
编辑于 2016-07-30 15:24:45
回复(1)
应该有两个步骤：
1.找到权值最大的位置和权值最小的位置；2.找到并统计他们到最近公共父节点的距离相加就能得到。
这就需要记录每个节点的父节点的一些信息，题目说明每个权值不同，但是没说明大小关系，因此不能只记录父节点的权值，这样的话最后没办法回溯父节点(不知道到底最大回溯还是最小回溯),所以用一个自增的int变量cnt来记录父节点的编号。这样对于父节点，要知道他的权值(回溯)，也要知道编号(回溯哪个)，因此父节点
数据类型可设置为：map<int,
pair<int,int>>parent;//节点权值，父节点权值，父节点编号。max和min为最大和最小节点的权值
借助队列，按层遍历，存储每个节点的父节点信息。
存储完成后，需要找到公共父节点。开始回溯：
回溯的终止条件是节点的权值相等：max=min
当发现max父节点的编号大于min父节点的编号时，max变为他的父节点:max=parent[max].first；
当发现min父节点的编号大于max父节点的编号时，min变为他的父节点:min=parent[min].first；
最后当他们父节点的编号相等时，说明他们的父节点是公共父节点。得到结论。
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;
}
发表于 2016-04-07 10:19:41
回复(0)
宽度优先遍历+深度优先遍历
整体思路不难，用BFS找到权值最大和最小的两个叶子节点，然后DFS抓出它两的最近公共祖先，最后计算公共祖先到它两的距离加起来就可以了。
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;
}
}
编辑于 2022-02-24 20:16:41
回复(0)
# -*- 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
发表于 2017-03-27 17:06:57
回复(0)
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();
}
}
}
发表于 2016-09-25 00:53:22
回复(0)
//后续遍历树，并打印从根节点到叶子节点的路径
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();
}
};
编辑于 2016-08-31 22:34:47
回复(0)
//这个题关键是找到最大结点和最小结点刚开始分叉的地方，也就是共有路径的结束点。那么最后的距离就等于（最大结点的路径长度-共有路径长度）+（最小结点的路径长度-共有路径长度）
//可以采取哈夫曼编码树的方法，记录从根结点到该结点的唯一路径。如：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();
}
};
编辑于 2016-08-02 13:29:22
回复(0)
http://www.cnblogs.com/hslzju/p/5718729.html
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <map>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//以前序遍历创建二叉树
void CreateBiTree(TreeNode **T)//*T是指向BiTNode的指针
{
*T=new TreeNode(0);
if(*T==NULL)//如果*T还是指向NULL，表示内存分配失败，退出程序
exit(OVERFLOW);
char ch;
cin>>ch;
if(ch=='#')
*T=NULL;
else
{
(*T)->val=ch-'0';//*T指向的节点的data分配内容，即生成根节点
CreateBiTree(&((*T)->left));//创建&(*T)->lchild临时变量，传入CreateBiTree，构造左子树
CreateBiTree(&((*T)->right));//创建&(*T)->rchild临时变量，传入CreateBiTree，构造右子树
}
}
/*
分两大步
1 标记每个节点的父节点，并且找出最大叶节点和最小叶节点
用map<int,pair<int,int>>标记每个子节点的父节点，first是子节点值，second是<父节点值，父节点位置>
用queue遍历二叉树的节点
依次把每个父节点的子节点push进队列，每取出一个节点处理，计数加1，然后处理取出节点的左右孩子进行标记
处理完之后，把取出的节点pop出去
2 计算两个叶节点的最短路径
分别找出两个叶节点到树根的路径，公共部分以前的路径相加即最短路径
*/
class Tree {
public:
int getDis(TreeNode* root)
{
// write code here
//第1步
map<int, pair<int, int>> parent;//标记每个子节点的父节点
queue<TreeNode*> que;//按照层序遍历处理每个节点
que.push(root);
parent[root->val] = make_pair(0, 0);//树根的双亲设置为(0,0)
int max = -65535;
int min = 65536;
int cnt = 0;//每处理一个节点计数加1
while (!que.empty())
{
//处理队列里的每个节点，每处理一个，计数加1。即cnt是目前处理的节点的序号（按层序遍历标序）。
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)//如果该节点是叶子节点，需要比较它和max和min的大小
{
if (temp->val > max)
max = temp->val;
if (temp->val < min)
min = temp->val;
}
que.pop();
}
//第2步
vector<int> v1;
vector<int> v2;
v1.push_back(min);
v2.push_back(max);
int move1 = min;
int move2 = max;
while(parent[move1].second > 0)//把min到树根的路径找出来
{
v1.push_back(parent[move1].first);
move1 = parent[move1].first;
}
while (parent[move2].second > 0)//把max到树根的路径找出来
{
v2.push_back(parent[move2].first);
move2 = parent[move2].first;
}
//反转一下方便查找公共串，第一个节点都是树根
reverse(v1.begin(), v1.end());
reverse(v2.begin(), v2.end());
int n = 0;
for (;v1[n] == v2[n];n++);//n是公共串的结尾
return (v1.size() + v2.size() - 2 * n);
}
};
//测试
int main()
{
TreeNode **pp;//定义指向BiTNode的二级指针pp
TreeNode *p;//定义指向BiTNode的指针p
pp=&p;//pp指向p
p=NULL;//初始化p指向NULL
CreateBiTree(pp);//传入指向p的地址，创建二叉树,输入5129###3##4#68##7##
Tree solution;
cout << solution.getDis(p);
return 0;
}
发表于 2016-07-29 16:02:28
回复(0)
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
编辑于 2016-03-30 17:51:04
回复(0)
//典型的二进制编码题，算出叶子节点二进制编码，再比编码，计算后缀长度和
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
}
发表于 2016-07-08 14:39:19
回复(16)
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 heregetMaxMin(root);//找到最大最小叶子节点TreeNode lcaNode = getLCA(root);//找LCAint 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;}
编辑于 2016-08-01 17:25:02
回复(3)
//受大神们的启发，找路径，然后去重，代码较短。时间复杂度应该就是遍历二叉树的复杂度。
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;
}
};
发表于 2016-12-21 12:23:56
回复(11)
Python版本，按照编码的思路解决问题！
class Tree: def __init__(self): self.max = 0 self.min = 99999 self.maxpath = [] self.minpath = [] def getDis(self, root): # write code here code = '' self.midOrder(root,'0',code) a = self.minpath b = self.maxpath for i in range(0,min(len(a),len(b))): if a[i] != b[i]: result = len(a[i:]+b[i:]) break return result def midOrder(self,root,Flag,code): if root == None: return code = code + Flag if root.left == None and root.right == None: if self.max < root.val: self.max = root.val self.maxpath = code if self.min > root.val: self.min = root.val self.minpath = code self.midOrder(root.left,'0',code) self.midOrder(root.right,'1',code)
发表于 2019-08-21 20:22:02
回复(0)
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));
}
}
}
想法就是层序遍历，用两个Map
一个Map record记录每个节点的深度。深度定义，根是0，左子树从1开始增加，右子树从-1开始减少
一个Map father记录每个节点的father
max,min记录最大最小
层序遍历二叉树，记录两个map和max min
最后从record中获取max和min对应的深度,若两个深度符号相反，直接相减取绝对值
若是符号相同，还要找共同的祖先，然后用共同祖先的深度减去他们两个的深度加在一起就是结果。
感觉差点就通不过了。。。让我来康康大家用的什么方法哈哈哈
发表于 2020-04-06 21:36:55
回复(0)
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');
}
}
发表于 2019-08-30 23:24:13
回复(0)
大致思路是要先找到最大值的叶子节点和最小值的叶子节点，然后从两个叶子节点向上，一直找两个叶子节点的共同的父节点，然后计算父节点分别到两个节点的距离，求和，就是这两个节点之间的距离
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 {
Map<TreeNode,TreeNode> map = new HashMap();//记录父节点
List<TreeNode> leaf = new ArrayList();//记录叶子节点
public int getDis(TreeNode root) {
TreeNode arr[] = max_and_min(root);//找到最大和最小的叶子节点
TreeNode node1 = arr[0];
TreeNode node2 = arr[1];
List<TreeNode> max_road = new ArrayList();//最大叶子节点的回溯路径
List<TreeNode> min_road = new ArrayList();//最小叶子节点的回溯路径
Map<TreeNode,Integer> len1 = new HashMap();//记录当前父节点到最大叶子节点的距离
Map<TreeNode,Integer> len2 = new HashMap();//记录当前父节点到最小叶子节点的距离
int t1=0,t2=0;//临时变量
while(node1!=null){
max_road.add(node1);
len1.put(node1,t1++);
node1 = map.get(node1);
}
while(node2!=null){
min_road.add(node2);
len2.put(node2,t2++);
node2 = map.get(node2);
}
TreeNode same_parent = null;//共同父节点
int tag = 0;
for(int i=0;i<max_road.size()&&tag==0;i++){//遍历找到相同的父节点
for(int j=0;j<min_road.size();j++){
if(max_road.get(i)==min_road.get(j)){
same_parent = max_road.get(i);
tag = 1;
break;
}
}
}
return len1.get(same_parent)+len2.get(same_parent);
}
public TreeNode[] max_and_min(TreeNode root){//广度优先遍历找到最大和最小叶子节点；
if(root==null)
return null;
List<Integer> list = new ArrayList();
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
map.put(root,null);
while(!queue.isEmpty()){
int size = queue.size();
while(size>0){
TreeNode temp = queue.poll();
if(temp.left==null&&temp.right==null){
list.add(temp.val);
leaf.add(temp);
}
if(temp.left!=null){
queue.offer(temp.left);
map.put(temp.left,temp);
}
if(temp.right!=null){
queue.offer(temp.right);
map.put(temp.right,temp);
}
size--;
}
}
TreeNode[] res = new TreeNode[2];
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i=0;i<list.size();i++){
if(max<list.get(i))
max = list.get(i);
if(min>list.get(i))
min = list.get(i);
}
TreeNode leaf_max=null,leaf_min=null;
for(int i=0;i<leaf.size();i++){
if(leaf.get(i).val==max){
leaf_max = leaf.get(i);
break;
}
}
for(int i=0;i<leaf.size();i++){
if(leaf.get(i).val==min){
leaf_min = leaf.get(i);
break;
}
}
res[0] = leaf_max;
res[1] = leaf_min;
return res;
}
}
发表于 2019-08-22 23:43:57
回复(0)
问题信息
通过挑战的用户
-
2023-02-16 15:14:33
-
2022-11-29 13:03:47
-
2022-11-27 00:39:19
-
2022-11-07 15:06:09 -
2022-09-22 13:48:56
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
