1000ms

Difficulty: 5

所属公司 : 蚂蚁

时间 :2025年9月18日

算法与标签>BFS

会员或题库专享

请先，开通会员或购买题库蚂蚁机考题库，可解锁完整内容。

购买蚂蚁机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（蚂蚁机考题库），可解锁完整内容。

购买题库开通会员

思路与结论

关键观察

由定义可知：每向下一层， $y$ 坐标减 $1$ ，因此对任意结点 $i$ ，有 $y_i = -\text{depth}(i),$ 其中 $\text{depth}(1)=0$ 。
$x$ 坐标从根开始：走到左儿子 $x$ 减 $1$ ，走到右儿子 $x$ 加 $1$ 。因而 $x_i$ 等于从根到 $i$ 的路径上“右转次数减去左转次数”。

题目内容

小红有一棵 $n$ 个结点的二叉树，根结点为1。

定义树上一个点的坐标为 $(xi,yi)$ ，根结点的坐标为 $(0,0)$ 。

一个结点若有两个子结点，那么我们称编号较小的结点为左儿子，编号较大的为右儿子，若只有一个结点，默认其为左儿子。