输出二叉树的右视图

/**1先构造二叉树
   2程序遍历
*/
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
public     List<Integer>list=new ArrayList<Integer>();
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        TreeNode head =dfs(xianxu,zhongxu);
        getRightList(head);
        int[]a=new int[list.size()];
        for(int i=0;i<list.size();i++){
            a[i]=list.get(i);
        }
       
        return a;
    }
    
    public TreeNode dfs(int[]xianxu,int[] zhongxu ){
        if(xianxu.length==0||zhongxu.length==0){
            return null;
        }
       
        TreeNode head= new TreeNode(xianxu[0]);
        if(xianxu.length==1||zhongxu.length==1){
            return head;
        }
       for(int i=0;i<zhongxu.length;i++){
           if(zhongxu[i]==xianxu[0]){
               head.left=dfs(Arrays.copyOfRange(xianxu,1,i+1),Arrays.copyOfRange(zhongxu,0,i));
               head.right=dfs(Arrays.copyOfRange(xianxu,i+1,xianxu.length),Arrays.copyOfRange(zhongxu,i+1,zhongxu.length));
           }
       }
       return head;
    }
    public void getRightList(TreeNode root){
      Queue<TreeNode> q=new LinkedList<TreeNode>();
        q.offer(root);
        while(!q.isEmpty()){
            int mount=q.size();
            for(int i=0;i<mount;i++){
                if(q.peek().left!=null)
                    q.offer(q.peek().left);
                if(q.peek().right!=null)
                    q.offer(q.peek().right);
                if(i==mount-1){
                    list.add(q.poll().val);
                }  else{
                    q.poll();
                } 
                
            }
              
        }
    }
 
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
 */
// 1、创建节点类型
function TreeNode(x) {
   this.val = x;
   this.left = null;
   this.right = null;
}
// 2、创建二叉树
function buildTree(xianxu, zhongxu) {
    if(xianxu.length === 0 || zhongxu.length === 0) {
        return null;
    }
    let root = new TreeNode(xianxu[0]);
    let index = zhongxu.indexOf(root.val);
    let leftPre = xianxu.slice(1, index + 1);
    let leftVin = zhongxu.slice(0, index);
    root.left = buildTree(leftPre, leftVin);
    let rightPre = xianxu.slice(index + 1);
    let rightVin = zhongxu.slice(index + 1);
    root.right = buildTree(rightPre, rightVin);
    return root;
}
// 3、输出二叉树的右视图
function printRight(root) {
    if(!root) {
        return [];
    }
    let res = [];
    let queue = [root];
    let index = 0;
    while(queue.length) {
        let len = queue.length;
        for(let i=0; i<len; i++) {
            let node = queue.shift();
            if(i === (len - 1)) {
                res[index] = node.val;
                index++;
            }
            if(node.left) {
                queue.push(node.left);
            }
            if(node.right) {
                queue.push(node.right);
            }
        }
    }
    return res;
}
function solve( xianxu ,  zhongxu ) {
    let root = buildTree(xianxu, zhongxu);
    let rightView = printRight(root);
    return rightView;
}
module.exports = {
    solve : solve
};

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        TreeNode root = reCons(xianxu, zhongxu);
        return bfs(root);
    }
    public TreeNode reCons (int[] xianxu, int[] zhongxu) {
        if(xianxu == null || xianxu.length == 0) return null;
        int val = xianxu[0], position = 0, len = xianxu.length;
        TreeNode root = new TreeNode(val);
        for(position = 0; position < len; position++) {
            if(zhongxu[position] == val) break;
        }
        root.left = reCons(Arrays.copyOfRange(xianxu, 1, position + 1), Arrays.copyOfRange(zhongxu, 0 , position));
        root.right = reCons(Arrays.copyOfRange(xianxu, position + 1, len), Arrays.copyOfRange(zhongxu,position + 1, len));
        return root;       
    }
    public int[] bfs (TreeNode root) {
        if(root == null) return null;
        List<Integer> ls = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int temp = 0;
        while(!q.isEmpty()) {
            int size = q.size();
            while(size > 0) {
                TreeNode t = q.poll();
                if(t.left != null) q.add(t.left);
                if(t.right != null) q.add(t.right);
                size--;
                temp = t.val;
            }
            ls.add(temp);
        }
        int[] res = new int[ls.size()];
        for(int i = 0; i < res.length; i++) {
            res[i] = ls.get(i);
        }
        return res; 
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        if (xianxu.length == 0 || zhongxu.length == 0){
            return null;
        }
        List<TreeNode> list = new ArrayList<>();
        TreeNode root = build(xianxu, zhongxu);

        //队列交换
        //指针cur永远指向不为空的队列
        Queue<TreeNode> cur = new LinkedList<>();

        //指针temp永远指向空的队列
        Queue<TreeNode> temp = new LinkedList<>();
        cur.offer(root);

        //cur指向的队列进行出队操作，temp指向的队列进行入队操作
        while (!cur.isEmpty()){
            TreeNode poll = cur.poll();
            if (cur.size() == 0){
                list.add(poll);
            }
            if (poll.left != null){
                temp.offer(poll.left);
            }
            if (poll.right != null){
                temp.offer(poll.right);
            }
            if (cur.isEmpty()){
                Queue<TreeNode> t = cur;
                cur = temp;
                temp = t;
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i).val;
        }
        return result;
    }
    private TreeNode build(int[] pre, int[] in){
        if (pre.length == 0 || in.length == 0){
            return null;
        }

        TreeNode root = new TreeNode(pre[0]);

        if (pre.length == 1 || in.length == 1){
            return root;
        }

        int rootIndex = 0;
        for (int i = 0; i < in.length; i++) {
            if (in[i] == root.val){
                rootIndex = i;
                break;
            }
        }
        root.left =
                build(Arrays.copyOfRange(pre, 1, rootIndex+1), Arrays.copyOfRange(in, 0, rootIndex));
        root.right =
                build(Arrays.copyOfRange(pre,rootIndex+1,pre.length),Arrays.copyOfRange(in,rootIndex+1,in.length));

        return root;
    }
}

function solve( xianxu ,  zhongxu ) {
    const root = buildTree(xianxu, zhongxu);
    const rightView = getRightView(root);
    return rightView;
}
function buildTree(xianxu, zhongxu) {
    if (xianxu.length === 0) return null;
    const root = new TreeNode(xianxu[0]);
    const index = zhongxu.indexOf(root.val);
    const lefts = zhongxu.slice(0, index);
    const rights = zhongxu.slice(index + 1);
    root.left = buildTree(xianxu.slice(1, lefts.length + 1), lefts);
    root.right = buildTree(xianxu.slice(lefts.length + 1), rights);
    return root;
}
function getRightView(root) {
    const res = [];
    let stack = [root];
    while (stack.length) {
        const rowLen = stack.length;
        const newStack = [];
        for (let i = 0; i < rowLen; i++) {
            const node = stack[i];
            if (i === stack.length - 1) res.push(node.val);
            if (node.left) newStack.push(node.left);
            if (node.right) newStack.push(node.right);
        }
        stack = newStack;
    }
    return res;
}

• 然后将左子树看作一棵新的树，但注意要将level + 1, 因为已经到了下一层。

• 对左子树操作完之后再操作右子树，这样的话，进行put(level, rootVal)运算时，同一level中，右边节点可以覆盖左边节点的值，最终得到的就是右视图！

import java.util.*;

public class Solution {
    private List<Integer> res;
    private int[] myPre;
    private int[] myIn;
    private int len;
    public int[] solve (int[] xianxu, int[] zhongxu) {
        res = new ArrayList<>();
        myPre = xianxu;
        myIn = zhongxu;
        len = xianxu.length;
        dfs(0, len - 1, 0, len - 1, 0);
        int[] ans = new int[res.size()]; // 转成数组返回
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }
    
    private void dfs(int start1, int end1, int start2, int end2, int level) {
        if (start1 > end1) {
            return;
        }
        int rootVal = myPre[start1]; // 当前根结点
        if (res.size() <= level) { // 说明当前是最左节点，只能add，不能覆盖
            res.add(rootVal);
        }
        else {
            res.set(level, rootVal); // 覆盖同一level中之前记录过的节点，最终保留的就是每一level的最右节点
        }
        for (int i = 0; i < len; i++) {
            if (myIn[i] == rootVal) { // 递归调用
                dfs(start1 + 1, start1 + i - start2, start2, i - 1, level + 1);
                dfs(start1 + i - start2 + 1, end1, i + 1, end2, level + 1);
                break;
            }
        }
    }
}

//先构建出二叉树，再打印出右视图
class Solution {
public:
    vector<int> ans;
    vector<int> solve(vector<int> &preorder, vector<int> &inorder) {
        int presize = preorder.size();
        int insize = inorder.size();
        if (presize != insize || presize == 0 || insize == 0)
            return ans;
        auto head = ReconstructTree(preorder, inorder, 0, presize - 1, 0, insize - 1);
        rightTree(head);
        return ans;
    }
    void rightTree(TreeNode *head) {
        queue<TreeNode *> q;
        q.push(head);
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto tmp = q.front();
                q.pop();
                if (tmp->left) q.push(tmp->left);
                if (tmp->right) q.push(tmp->right);
                if (i == size - 1) ans.push_back(tmp->val);
            }
        }
    }
    TreeNode *ReconstructTree(vector<int> &preorder, vector<int> &inorder, int pl, int pr, int il, int ir) {
        auto *root = new TreeNode(preorder[pl]);
        if (pl == pr) return root;
        int index = 0;
        for (int i = il; i <= ir; i++) {
            if (inorder[i] == preorder[pl]) {
                index = i;
                break;
            }
        }
        int ltreelen = index - il;
        int rtreelen = ir - index;
        if (ltreelen > 0) root->left = ReconstructTree(preorder, inorder, pl + 1, pl + ltreelen, il, index - 1);
        if (rtreelen > 0) root->right = ReconstructTree(preorder, inorder, pl + 1 + ltreelen, pr, index + 1, ir);
        return root;
    }
};

先把树构建出来，在通过队列取出每层的最后一个节点的值
时间复杂度：O(n) 空间复杂度：O(n)

class Solution:
    def tree(self, pre, vin):
        if not pre:
            return None
        root = TreeNode(pre[0])
        tem = vin.index(pre[0])
        root.left = self.tree(pre[1:tem+1], vin[:tem])
        root.right = self.tree(pre[tem+1:], vin[tem+1:])
        return root
    def solve(self , pre: List[int], vin: List[int]) -> List[int]:
        res = []
        root = self.tree(pre, vin)
        q = [root]
        while q:
            n = len(q)
            for i in range(n):
                cur = q.pop(0)
                if i == n-1:
                    res.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
        return res

不构造树，利用map 直接得出右视图！

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        Map<Integer,Integer> map = new HashMap<>();
        if (xianxu.length == 0 || xianxu.length != zhongxu.length) return new int[0];
        findU(xianxu, zhongxu, 0, xianxu.length - 1, 0, zhongxu.length - 1, map, 0);
        int[] res = new int[xianxu.length];
        int len = 0;
        Integer temp;
        while ((temp = map.get(len)) != null) {
            res[len++] = temp;
        }
        return Arrays.copyOf(res, len);
        // write code here
    }
    
    private void findU(int[] xianxu, int[] zhongxu, int xleft, int xright,
                       int zleft, int zright, Map<Integer, Integer> map, int level) {
        if (xleft > xright || zleft > zright) return;
        int p = xianxu[xleft];
        int i = zleft;
        for (; i <= zright && zhongxu[i] != p; i++);
        // 如果存在则说明构建右节点的时候已经放进去了
        if (!map.containsKey(level))
            map.put(level, p);
        // 先构建右边的结点  i - zleft代表左节点有多少个
        findU(xianxu, zhongxu, xleft + (i - zleft) + 1, xright, i + 1, zright, map, level + 1);
        // 构建左结点
        findU(xianxu, zhongxu, xleft + 1, xleft + (i - zleft), zleft, i - 1, map, level + 1);
    }
}

class Solution:
    def solve(self , preOrder: List[int], inOrder: List[int]) -> List[int]:
        if not preOrder:
            return []
        res = [preOrder[0]]
        index = inOrder.index(preOrder[0])
        # 左子树的右视图
        left = self.solve(preOrder[1:index+1], inOrder[:index])
        # 右子树的右视图
        right = self.solve(preOrder[index+1:], inOrder[index+1:])
        # 优先取右子树，剩余取左子树
        return res + right + left[len(right):]

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    
    TreeNode* reBuild(vector<int>& pre, vector<int>& in)
    {
        int len = pre.size();
        if(!len)
        {
            return NULL;
        }
        int root_val = pre[0];
        TreeNode* root = new TreeNode(root_val);
        int left_len = -1;
        for(int i = 0; i < len; i++)
        {
            if(in[i] == root_val)
            {
                left_len = i;
                break;
            }
        }
        vector<int> pre_left(pre.begin() + 1, pre.begin() + 1 + left_len);
        vector<int> pre_right(pre.begin() + 1 + left_len, pre.end());
        vector<int> in_left(in.begin(), in.begin() + left_len);
        vector<int> in_right(in.begin() + left_len + 1, in.end());
        root->left = reBuild(pre_left, in_left);
        root->right = reBuild(pre_right, in_right);
        return root;
    }
    vector<int> solve(vector<int>& pre, vector<int>& in) {
        // write code here
        TreeNode* root = reBuild(pre, in);
        vector<int> res;
        if(!root)
        {
            return res;
        }
        queue<TreeNode*> q;
        q.push(root);
        
        while(!q.empty())
        {
            int len = q.size();
            TreeNode* node;
            for(int i = 0; i < len; i++)
            {
                node = q.front();
                q.pop();
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            res.push_back(node->val);
        }
        return res;
        
    }
};

class Solution {
private:
    unordered_map<int, int> mp;
public:
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        for(int i=0; i<zhongxu.size(); ++i) {
            mp[zhongxu[i]] = i;
        }
        TreeNode* root = rebuild(xianxu, zhongxu, 0, xianxu.size()-1, 0, zhongxu.size()-1);
        vector<int> res = levelOrder(root);
        return res;
    }
    
    TreeNode* rebuild(vector<int>& preOrder, vector<int>& inOrder, int p1, int p2, int i1, int i2) {
        if(p1>p2) return nullptr;
        TreeNode* node = new TreeNode(preOrder[p1]);
        int r = mp[node->val];
        node->left = rebuild(preOrder, inOrder, p1+1, p1+r-i1, i1, r-1);
        node->right = rebuild(preOrder, inOrder, p1+r-i1+1, p2, r+1, i2);
        return node;
    }
    
    vector<int> levelOrder(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int size = q.size();
            for(int i=0; i<size; ++i) {
                TreeNode* node = q.front();
                q.pop();
                if(i==size-1) res.push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        return res;
    }
};

#include <queue>
#include <sys/types.h>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    TreeNode* reconstTree(vector<int>& preOrder, vector<int>& inOrder) {
        int m = preOrder.size();
        int n = inOrder.size();
        if (m == 0 || n == 0) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(preOrder[0]);
        for (int i = 0; i < n; i++) {
            if (preOrder[0] == inOrder[i]) {
                vector<int> leftpre(preOrder.begin() + 1, preOrder.begin() + i + 1);
                vector<int> leftin(inOrder.begin(), inOrder.begin() + i);
                root->left = reconstTree(leftpre, leftin);
                vector<int> rightpre(preOrder.begin() + i + 1, preOrder.end());
                vector<int>  rightin(inOrder.begin() + i+1, inOrder.end());
                root->right = reconstTree(rightpre, rightin);
                break;
            }
        }
        return  root;
    }
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        //首先重建二叉树
        TreeNode* root = reconstTree(preOrder, inOrder);
        queue<TreeNode*> q;
        q.push(root);
        vector<int>  res;
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
                if (i == sz - 1) {
                    res.push_back(node->val);
                }
            }
        }
        return  res;

    }
};

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
        List<Integer> result = new ArrayList<>();
        if (preOrder.length < 1 || preOrder.length != inOrder.length) {
            return null;
        }
        // 根据前序遍历和中序遍历构造二叉树
        TreeNode root = buildTree(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
        if (root == null) {
            return null;
        }
        // 使用迭代法寻找二叉树的最右侧节点
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        while (!queue.isEmpty()) {
            // 求出每层节点的数量
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.removeFirst();
                // size - 1即为最右侧节点，加入到result结果列表中
                if (i == size - 1) {
                    result.add(node.val);
                }
                if (node.left != null) {
                    queue.addLast(node.left);
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                }
            }
        }
        return result.stream().mapToInt(x -> x).toArray();
    }

    // 根据前序遍历和中序遍历构造二叉树
    public TreeNode buildTree(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        int root_val = preOrder[preStart];
        TreeNode root = new TreeNode(root_val);
        int index = 0;
        for (index = 0; index < inOrder.length; index++) {
            if (inOrder[index] == root_val) {
                break;
            }
        }
        int left_length = index - inStart;
        root.left = buildTree(preOrder, preStart + 1, preStart + left_length, inOrder, inStart, index - 1);
        root.right = buildTree(preOrder, preStart + left_length + 1, preEnd, inOrder, index + 1, inEnd);
        return root;
    }
}