二叉树-遍历

能帮到你的话，就给个赞吧 😘

二叉树遍历

是否可以通过遍历节点得出答案(浅)

遍历模板

void traverse(TreeNode* root){

        if(!root)
            return ;
	
        traverse(root->left);
        traverse(root->right);
    }

题单01(容易)

有些问题，非常容易看出可以通过遍历节点而得到

01 144. 二叉树的前序遍历

02 5. N 叉树的前序遍历

03 226. 翻转二叉树

遍历节点并翻转

04 404. 左叶子之和

遍历左叶子并相加

05 104. 二叉树的最大深度

遍历节点并更新最大深度

06 559. N 叉树的最大深度

07 111. 二叉树的最小深度

遍历叶子节点并更新最小深度

08 112. 路径总和

遍历路径并判断(路径当然可以通过遍历节点而来)

路径:根节点到叶子节点

09 113. 路径总和 II

遍历路径并保存

10 515. 在每个树行中找最大值

遍历节点并更新其所在行最大值

11 102. 二叉树的层序遍历

遍历节点并存储进所在层

12 938. 二叉搜索树的范围和

遍历节点并判断其是否在范围内

13 116. 填充每个节点的下一个右侧节点指针

遍历节点并填充
此题主要在于填充

14 257. 二叉树的所有路径

遍历路径并添加
此题主要在于string path的撤销

15 129. 求根节点到叶节点数字之和

遍历路径并求和

16 1022. 从根到叶的二进制数之和

同129

17 199. 二叉树的右视图

遍历最右侧节点

18 988. 从叶结点开始的最小字符串

遍历字符串并比较
此题主要在于字符串是从叶子节点到根节点

字典序:由字母组成
string.compare 比较字典序

19 1457. 二叉树中的伪回文路径

遍历路径判断是否为伪回文

回文:出现次数为奇数的元素数<=1

20 617. 合并二叉树

遍历节点判断是否可以合并。

21 623. 在二叉树中增加一行

遍历上一行的节点并增加

22 971. 翻转二叉树以匹配先序遍历

遍历节点判断是否可以翻转。
注意点:前序遍历不能定位其子节点，但可以定位其左子节点。leftID = rootID + 1

23 572. 另一棵树的子树

遍历节点判断其子树是否相同

24 993. 二叉树的堂兄弟节点

判断x,y是否为堂兄弟

25 1315. 祖父节点值为偶数的节点和

遍历节点判断其祖父是否为偶数

26 1448. 统计二叉树中好节点的数目

遍历节点判断是否为好节点

27 987. 二叉树的垂序遍历*

28 513. 找树左下角的值

寻找左下角节点

29 1261. 在受污染的二叉树中查找元素

遍历节点还原污染即可

Tips:
	遍历过程中用集合存储节点

题单01(稍微不容易)

01 437. 路径总和 III

遍历每个节点，求每个节点的树的路径
技巧:区域和-前缀和

03 124. 二叉树中的最大路径和

会员

01 298. 二叉树最长连续序列🔒

02 1430. 判断给定的序列是否是二叉树从根到叶的路径🔒

03 270. 最接近的二叉搜索树值🔒

04 666. 路径总和 IV🔒

05 1469. 寻找所有的独生节点🔒

06 1602. 找到二叉树中最近的右侧节点🔒

遍历代码注意事项

容器注意事项

1. string path并不能准确修改现场与撤销现场，因此一般用vector<string>替代string再统一处理 详见257
2. string path可以+= char或string, 但to_string和char则对同一int返回不一样的结果。若要+=某一字母则应用char 详见988
3. 空串的字典序 > 非空串，要单独处理. 详见988