#10290. 二叉树的深度优先遍历(标记变化)
二叉树的深度优先遍历(标记变化)
题目 1:二叉树的深度优先遍历(标记变化)
问题描述:
给定一个深度为 depth
的二叉树和一个整数 k
,你需要进行 k
次从根节点开始的深度优先遍历。每次遍历时,根据以下规则更新树的节点状态:
- 如果当前节点未被访问过,则访问左子节点(编号为
2 * 当前节点编号
)。 - 如果当前节点已经被访问过,则访问右子节点(编号为
2 * 当前节点编号 + 1
)。
你需要计算并输出 k
次遍历后的最后访问节点编号。
输入格式:
- 输入两个整数
depth
和k
(1<=depth<=20 ),( 1 <=k <=10^5 ,表示树的深度和 DFS 执行的次数。
输出格式:
- 输出最终的节点编号
ans
,即执行k
次 DFS 后的最后一个访问节点。
示例 1:
输入:
4 3
输出:
10
示例 2:
输入:
3 2
输出:
6