1.20 learning summary

Today I'm going to solve the problem again . What I want to say today is a Through the program to determine the depth of the binary tree . The specific topics are as follows .

The way I did this problem . Is to build a binary tree directly from a structure . To find the depth by preorder traversal .

One was used max function .  And used a deep Variable to record the current depth . max Function is to get the maximum value of each time   In this way, you can find the depth after traversing the entire function .

The specific code is as follows ,

 

#include<stdio.h>
#include <algorithm>
using namespace std;
struct node {
    int left, right;
};
node tree[10000000];

int n, ans;

void dfs(int d, int deep) {
    if (d == 0) return ; 
    ans = max(ans, deep); 
    dfs(tree[d].left, deep+1); 
    dfs(tree[d].right, deep+1);// Use preorder to traverse 
}

int main() {
    scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&tree[i].left,&tree[i].right);// A forest is represented by a structure .
		} 
    dfs(1, 1); 
    printf("%d",ans);
    return 0; 
}

Of course, my code has a little logic problem .  This code cannot find the root node .  That is to say, the first input must be the root node .  I solved this problem while working on another topic .  But when I read this topic , Didn't study it carefully .  When I was doing another topic , That solves the problem . Specifically speaking ？ Is to create an additional data field to store . Their root node   It is equivalent to each subtree .  Stored their last node .  That is, relative to their root node .  In this case , There are only root nodes in the whole tree , There is no ancestor .  You can find the root node in the structure .

Now that it's all here , Just solve the problem . Did it, too . The title is as follows .

  And the solution to this problem I also said a little . The only thing to add is that the elements here are mostly characters ,  Or all letters .  Then I use the method of forced transformation . Turn them into int type   Thus, the subscript of the lower structure can be used ,

Then the way to store the number of pieces .  It's what I call building three data fields ,  Store his ancestors separately . And left and right nodes .  And then traverse it . Then the general idea is like this .  The code is as follows ,

 #include<stdio.h>
 #include<string.h>
 #include<iostream>
 using namespace std;
 struct node{          
     char left,right,ss;    
 };
 node tree[1000];
 void dfs(char s)
 {                              
     printf("%c", s);
     if (tree[s].left!='*') dfs(tree[s].left);
     if (tree[s].right!='*') dfs(tree[s].right);
 }
 int main()
 {
     int i,n;
     char c,f1;
     char d[10000];
     cin>>n;
     for (i=1;i<=n;i++){     
         cin>>c;
         d[i]=c;
         cin>>tree[c].left>>tree[c].right;
         tree[tree[c].left].ss = tree[tree[c].right].ss = c;
     }for(i=1;i<=n;i++){
	 	if(tree[d[i]].ss==0){
		 	f1=d[i];
		 }
	 }
     dfs (f1);
     return 0;
 }

That's all for today's summary  . I will also work out all the solutions for these days .  I will do my best , The work was done in detail .   It is also the second time to understand these topics .