题解 | JAVA #输出二叉树的右视图# [P2]

跟精华解法里第二个HashMap的一样思路 JAVA版

类似于用preOrder和inOrder重构一个right-first-preOrder traversal.
https://blog.nowcoder.net/n/983254e186b2484c855622e68136bbc6

在recurse的同时记录当前node的层数，然后print该层第一个visit到的node.
因为是right-first-preOrder, 每层第一个visit的noded就是最右边的node.

import java.util.*;

public class Solution {
 
    public int[] solve (int[] xianxu, int[] zhongxu) {
      if (xianxu.length <= 1) return xianxu;

      int treeSize = xianxu.length;
      // maps level -> rightMostValue
      ArrayList<Integer> ans = new ArrayList<>();
      
      // maps zhongxu的 val -> index
      Map<Integer, Integer> hashM = new HashMap<>();
      for (int i=0; i < treeSize; i++) {
        hashM.put(zhongxu[i], i);
      }
      rec(0, treeSize-1, 0, treeSize-1, 0, xianxu, zhongxu, hashM, ans);
      return ans.stream().mapToInt(i->i).toArray();
    }
  
    // Handles the tree represented by xianxu[xS, xE] and zhongxu[zS, zE].
    void rec(int xS, int xE, int zS, int zE, int level, 
             int[] xianxu, int[] zhongxu, Map<Integer, Integer> hashM,
             ArrayList<Integer> ans) {
      // basecase1
      if (xS > xE) return;
      
      int rootVal = xianxu[xS];
      if (level == ans.size())
        ans.add(rootVal);  // only set ans[level] once.
      
      // basecase2
      if (xS == xE) return;
      
      int zxRootIdx = hashM.get(rootVal);
      int rightSubtreeSize = zE - zxRootIdx;
      int leftSubtreeSize = zxRootIdx - zS;
      
      // 先走right subtree，因为要右视图。
      rec(xE - rightSubtreeSize + 1, xE, zxRootIdx+1, zE, level+1, 
          xianxu, zhongxu, hashM, ans);
      rec(xS+1, xS+leftSubtreeSize, zS, zxRootIdx-1, level+1,
          xianxu, zhongxu, hashM, ans);
    }
}