P4913 【深基16.例3】二叉树深度 dfs-二叉树的遍历

P4913 【深基16.例3】二叉树深度
来源：

文章目录

• • 题目
  • 思路
  • 参考代码

题目

思路

从根节点开始往下搜索到叶子结点每一种可能的路径，然后找到长度最长的路径长度即为深度-即遍历这棵树

1. 如何储存该图，每个结点给出孩子节点，因此可以直接结构体储存孩子节点，结构体的下标就为该节点的序号
2. 如何从根节点开始搜索，直接从根节点开始玩往下搜索其孩子结点（先递归遍历该节点的左节点，再递归遍历该节点的右节点。），并及时记录本次搜索所在的路径长度（深度）- 搜完求最大值即为结果
3. 递归搜索-dfs退出条件：搜到叶子结点位置return

因为每个节点遍历一次，所以总时间复杂度为O(n) 运行时间安全

参考代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+5;intans=1;structnode{intl;intr;}tree[N];voiddfs(intx,intk);intmain(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>tree[i].l>>tree[i].r;}dfs(1,1);//深搜遍历结点，初始深度为1cout<<ans;return0;}voiddfs(intx,intk){if(x==0){//节点搜索到叶节点则停止return;}ans=max(ans,k);dfs(tree[x].l,k+1);//搜索左子树dfs(tree[x].r,k+1);//搜索右子树}