Binary tree path

Title Description

There is a binary tree, each point on the tree is marked with weight, and the weight is different. Please design an algorithm to calculate the distance between the leaf node with the largest weight and the leaf node with the smallest weight. The distance between each edge of a binary tree is 1, and the distance between the two nodes is how many sides a node passes to reach the other node.
Given the root node root of the binary tree, please return the distance.

Solving problems

Basic idea: first, traverse the binary tree, find the location of the largest and smallest leaf node, and then find the smallest common ancestor of both (the smallest ancestor here refers to the ancestor closest to the two nodes).
Method 1: to find the location of the largest and smallest leaf node, we need to traverse the entire binary tree, find the common ancestor, which can start from one node, trace upward, and mark the visited node. In the process of tracing upward, another node can stop when it encounters the visited node, and the steps of two nodes to reach this node are the distance length.
Method 2: when looking for the largest and smallest leaf node, record its path at the same time, then compare the two paths, remove the common part, and the rest is the distance between the two nodes.

code implementation

Method 1:

#include <iostream>
#include <vector>
#include <limits>
using namespace std;
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

class Tree {
public:	
    int getDis(TreeNode* root) {
        // write code here
	    vector<int> indexs;
        vector<int> weights;
		int maxn_index,minn_index;
		Traverse(root,indexs,weights,maxn_index,minn_index);
		int distance=getDisByIndex(maxn_index,minn_index,indexs);
		return distance;
    }
	void Traverse(TreeNode* root,vector<int>& indexs,vector<int>& weights,int& maxn_index,int& minn_index){
		if(root==NULL) return;
		vector<TreeNode*> nodes;
		maxn_index=-1;
		minn_index=-1;
		int minn = numeric_limits<int>::max();
        int maxn = numeric_limits<int>::min();
        nodes.push_back(root);
		indexs.push_back(-1);
		weights.push_back(root->val);
		TreeNode *left,*right,*current;
		int i=-1;
		while(!nodes.empty()){
			current=nodes[0];
			nodes.erase(nodes.begin());
			i++;
			left=current->left;
			right=current->right;
			if(left==NULL && right==NULL){			
				if(minn>current->val){
					minn=current->val;
					minn_index=i;
				}
				if(maxn<current->val){
					maxn=current->val;
					maxn_index=i;
				}
			}
			if(left!=NULL){
				nodes.push_back(left);
				indexs.push_back(i);
				weights.push_back(left->val);
			}
			if(right!=NULL){
				nodes.push_back(right);
				indexs.push_back(i);
				weights.push_back(right->val);
			}
		}


	}

	int getDisByIndex(int maxn_index,int minn_index,vector<int>& indexs){
		if(maxn_index==minn_index) return 0;
		vector<int> visit;
		int n=indexs.size();
		visit.resize(n,-1);
		int step=0;
		int pmax,pmin;
		pmax=maxn_index;
		while(pmax!=-1){
			if(visit[pmax]==-1){
				visit[pmax]=step++;
				pmax=indexs[pmax];
			}
		}
		int cnt=0;
		pmin=minn_index;
		while(pmin!=-1){
			if(visit[pmin]!=-1){
				return cnt+visit[pmin];
				}
			pmin=indexs[pmin];
			cnt++;
		}
	}
}

Method two:

#include <iostream>
#include <limits>
using namespace std;
struct TreeNode{
	int val;
	TreeNode *left,*right;
	TreeNode(int x):val(x),left(NULL),right(NULL){}
}
class Solution{
	public:
	int minn,maxn;
	vector<int> minn_path,maxn_path;
	int getDis(TreeNode* root){
	
		minn=limits<int>::max();
		maxn=limits<int>::min();
		vector<int> vec;
		dfs(root,vec);
		
		for(int i=0;;i++){
			if(minn_path[i]==maxn_path[i])
				continue;
			else
				return minn_path.size()-i+maxn_path.size();
		}
		
	}
	void dfs(TreeNode* root,vector<int>& vec){
		if(root==NULL)return;
		if(root->left==NULL && root->right==NULL){
			if(minn>root->val){
				minn=root->val;
				minn_path.assign(vec.begin(),vec.end());
			}
			if(maxn<root->val){
				maxn=root->val;
				maxn_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();
	}
}

The idea of this question is very clear. Just make it clear. But I spent half a day showing that I can't pass the test case. I'm sure that the method is OK, debugging to doubt life... Later, I found that the topic is the largest and smallest leaf node, and what I do is the largest and smallest node!!!

Published 6 original articles, won praise 0, visited 162
Private letter follow

Tags: REST

Posted on Sat, 08 Feb 2020 02:54:54 -0800 by edgev