Data-Structure_Algorithms_Coding/tree_leaf.cpp at main · Sdccoding/Data-Structure_Algorithms_Coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// int rec(TreeNode* A,int &B)
// {
//     if(A==NULL)
//      return 0 ;
//     rec(A->left,B,res);
//     if(B==0)
//     return A->val;
//     B--;
//     rec(A->right,B,res);

// }


int dist=INT_MAX; int aq=-1;
void ans(TreeNode* A,map<TreeNode*,TreeNode*> &mp,int dis,set<TreeNode*> &st)
{
     if(A==NULL)
       return ;

    //  cout<<A->val<<endl;
      st.insert(A);

     if(A->left==NULL && A->right==NULL)
     {
          if(dis<=dist)
          {
              aq=A->val;
              dist=dis;
          }
     }
     if(A->left && st.find(A->left)==st.end())
     {
             st.insert(A->left);
             ans(A->left,mp,dis+1,st);
     }
     if(A->right && st.find(A->right)==st.end())
     {
            st.insert(A->right);
            ans(A->right,mp,dis+1,st);
     }


     if(mp[A]!=NULL && st.find(mp[A]) == st.end())
       ans(mp[A],mp,dis+1,st);


}

void fi(int B,map<TreeNode*,TreeNode*> &mp,TreeNode* A,TreeNode* par,TreeNode* &value)
{
     if(A==NULL)
      return ;
      mp[A]=par;
      if(A->val == B)
      {
          value = A;
      }
      fi(B,mp,A->left,A,value);
      fi(B,mp,A->right,A,value);

}
int Solution::kthsmallest(TreeNode* A, int B) {

    TreeNode* value=NULL;
    aq=-1;
    map<TreeNode*,TreeNode*>mp;
    set<TreeNode*>st;

     fi(B,mp,A,NULL,value);
     //pre(A);
    cout<<"Value is "<<value->val<<endl;

     ans(value,mp,0,st);
     return aq;


}