二叉树最长路径问题

    （1）建立栈：
    //根据先序遍历建立，存在回溯现象，想到栈（如果按照层次遍历是队列）
    Node 包括左右指针，值data,还有访问次数visit_time
    对于一个Node，每次访问到它，visit_time++,当第三次访问到它，也就是左右节点都满了，这个时候它出栈。
    （2）根节点入栈
    （3）for(int i=1;i<n;i++){//表示对输入的字符串逐个访问
          	栈顶元素visit_time++;
         	 while(栈顶元素visit_time==3){ 
         	 //注意这里不是if 因为后续存在连续上溯，连续pop过程
          	pop 栈顶元素
         	 栈顶元素visit_time++;
         	 //这句别忘，因为上一个栈顶元素出栈后，
         	 //当前元素是下一个元素的儿子，所以对于下一个元素进行了访问。
          }
          	if(pre[I]!='flag'){  //flag 为空节点标志，此处为"#",pre为给定的先序遍历字符串
    	          	if(栈顶元素visit_time = =1)成为栈顶元素左子树
    	          	else 成为栈顶元素左子树
          }
          当前元素入栈
    }
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    
    代码解释

    #include <iostream>
    #include<stack>
    #include<vector>
    using namespace std;
    template<class Type>
    class BinaryTree{
    private:
    struct Node{//二叉树的结点类
        Node*left,*right;
        Type data;
        int visit_time;
        Node():left(NULL),right(NULL){}
        //参数化列表，内置结构体，结构体也可以有函数，不同之处：结构体定义中默认情况下的成员是public，而类定义中的默认情况下的成员是private的。
        Node(Type item,Node *L=NULL,Node *R=NULL,int visit_time=0):data(item),left(L),right(R),visit_time(0){}
    };
    Node *root;//二叉树的根节点
    public:
    BinaryTree():root(NULL){}//其实里面的元素就只有一个根节点，内置类不用管他。
    void clear(){
           if(root!=NULL) clear(root);//防止到私有函数那里对于左子树和右子树的访问失败。
           root=NULL;
       }
    ~BinaryTree(){clear();}  //有了new，要自己写析构函数，析构一般用clear;clear写在后面也可以哦
    
    
    void Create(Type flag,string s){
        stack<Node*> st;
        root=new Node(s[0]);
        st.push(root);
        for (int i=1; i<s.length(); i++) {
            st.top()->visit_time++;
            while (st.top()->visit_time>=3) {
           //     cout<<"pop"<<st.top()->data<<endl;
                st.pop();
                st.top()->visit_time++;
               // continue;
            }
            
                if (s[i]!=flag) {
                    Node* tmp=new Node(s[i]);
                    if (st.top()->visit_time==1)  st.top()->left=tmp;
                    else st.top()->right=tmp;
                    st.push(tmp);
                }
            }
        
    }
       
        vector<Node*> find_max_depth(Node *t){
           vector<Node*>lv;vector<Node*>rv;vector<Node*>v;
            if(t==NULL)return v ;//注意:1.判空!!而且放在最前面，不然下一句会爆掉
            else {
                lv=find_max_depth(t->left);
                rv=find_max_depth(t->right);
                if(lv.size()>=rv.size()){
                    lv.insert(lv.begin(), t);
                    return lv;
                }
                else{
                    rv.insert(rv.begin(), t);
                    return rv;
                }
            }
        }
        
    
    void find_max_depth(){
        vector<Node*> v =find_max_depth(root);
        cout<<v.size()<<endl;
        for(int i = 0; i != v.size(); i++){
            cout<<v[i]->data;
        }
    }
    private:
    void clear(Node *t){  //递归妙哉！！
        if(t->left!=NULL)clear(t->left);
        if(t->right!=NULL)clear(t->right);
        delete t;
    }
    };
    
    
    int main() {
    BinaryTree<char>tree;string s;
    cin>>s;
    tree.Create('#', s);
    tree.find_max_depth();
    return 0;
    }
    
    
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    
    代码解释