【新视角】输出二叉树的右视图

求解代码

// 存储最终结果：key = 二叉树的层级（根节点在第0层），value = 该层级【最右侧】的节点值privateHashMap<Integer,Integer>ans=newHashMap<>();// 预处理哈希表：key=中序数组的节点值，value=该值在中序数组的下标privateHashMap<Integer,Integer>map=newHashMap<>();// 前序数组的全局遍历指针：按「根→左→右」的前序规则，依次取当前递归层的根节点，取完自增privateintlevel=0;publicvoidbuildTree(int[]preOrder,int[]inOrder,intleft,intright,inti){if(left>right){return;}// 按前序顺序取根节点，通过哈希表拿到根节点在中序数组的下标indexintindex=map.get(preOrder[level++]);// 递归构建左子树，中序区间[left, index-1]，子节点层级 = 父层级+1buildTree(preOrder,inOrder,left,index-1,i+1);// 递归构建右子树，中序区间[index+1, right]，子节点层级 = 父层级+1buildTree(preOrder,inOrder,index+1,right,i+1);// 存入当前节点到对应层级，后存的节点会覆盖先存的 → 最终保留该层最右侧节点ans.put(i,inOrder[index]);}publicint[]solve(int[]preOrder,int[]inOrder){for(inti=0;i<inOrder.length;i++){map.put(inOrder[i],i);}buildTree(preOrder,inOrder,0,preOrder.length-1,0);int[]temp=newint[ans.size()];for(inti=0;i<ans.size();i++){temp[i]=ans.get(i);}returntemp;}

小贴士

解释一下这行代码ans.put(i, inOrder[index]);可以拿到「每层最右侧」的节点：

因为在递归时，是先递归构建左子树，再递归构建右子树，这个顺序意味着：在同一层级中，「左侧节点」会被先处理，「右侧节点」被后处理。

对于哈希表来说，相同key的put操作，会覆盖原值，在同一层级中，不管有多少个节点，最终只会存最后一次 put 的那个值。

所以，同一层级的右侧节点一定是最后一个被put的，所以最终ans.get(i)拿到的，一定是「第 i 层最右侧的节点值」。