我的DFS
void DFS(Node* root){if(root==NULL)return;if(root->lchild){root->lchild->layer = root->layer+1;cnt[root->lchild->layer] ++;maxLayer = max(maxLayer,root->lchild->layer);DFS(root->lchild);}if(root->rchild){root->rchild->layer = root->layer+1;cnt[root->rchild->layer] ++;maxLayer = max(maxLayer,root->rchild->layer);DFS(root->rchild);}
}
柳婼仙女的DFS
void DFS(Node* root,int depth){if(root==NULL){maxLayer = max(maxLayer,depth);return;}cnt[depth] ++;DFS(root->lchild,depth+1);DFS(root->rchild,depth+1);
}
注意:对左右子结点进行DFS之前不可以判空,否则maxLayer永不会更新!
AC代码
#include<cstdio>
#include<iostream>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>using namespace std;const int maxn = 1001;int n;
int cnt[maxn] = {0};
int maxLayer = -1;struct Node{int v;Node *lchild,*rchild;
};void insert(Node* &root,int x){if(root==NULL){root = new Node;root->v = x;root->lchild = root->rchild = NULL;return;}if(x<=root->v)insert(root->lchild,x);if(x>root->v)insert(root->rchild,x);
}void DFS(Node* root,int depth){if(root==NULL){maxLayer = max(maxLayer,depth);return;}cnt[depth] ++;DFS(root->lchild,depth+1);DFS(root->rchild,depth+1);
}int main(){cin>>n;Node* root = NULL;for(int i=0;i<n;i++){int x;cin>>x;insert(root,x);}DFS(root,0);printf("%d + %d = %d\n",cnt[maxLayer-1],cnt[maxLayer-2],cnt[maxLayer-1]+cnt[maxLayer-2]);return 0;
}