#10290. 二叉树的深度优先遍历(标记变化)

二叉树的深度优先遍历(标记变化)


题目 1:二叉树的深度优先遍历(标记变化)

问题描述:

给定一个深度为 depth 的二叉树和一个整数 k,你需要进行 k 次从根节点开始的深度优先遍历。每次遍历时,根据以下规则更新树的节点状态:

  • 如果当前节点未被访问过,则访问左子节点(编号为 2 * 当前节点编号)。
  • 如果当前节点已经被访问过,则访问右子节点(编号为 2 * 当前节点编号 + 1)。

你需要计算并输出 k 次遍历后的最后访问节点编号。

输入格式:

  • 输入两个整数 depthk(1<=depth<=20 ),( 1 <=k <=10^5 ,表示树的深度和 DFS 执行的次数。

输出格式:

  • 输出最终的节点编号 ans,即执行 k 次 DFS 后的最后一个访问节点。

示例 1:

输入:

4 3

输出:

10

示例 2:

输入:

3 2

输出:

6