【面试】算法题之二叉树右视图（并构建二叉树）

落神

看见很多大佬分享了一些算法，最近自己也在准备找实习，也来发一发。

构建二叉树：迭代
右视图：BFS+队列

[Java] 纯文本查看 复制代码

import java.util.*;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * xianxu int整型一维数组 先序遍历
     * zhongxu int整型一维数组 中序遍历
     * int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        if(xianxu.length == 0 || zhongxu.length == 0)
            return null;
        //构建二叉树
        TreeNode root = buildTree(xianxu,zhongxu);
        //右视图  层次遍历 只保存最后一个节点
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode node = queue.poll();
                if(i == size-1)
                    list.add(node.val);
                if(node.left != null)
                    queue.add(node.left);
                if(node.right != null)
                    queue.add(node.right);
            }
        }
        int[] result = new int[list.size()];
        for(int i=0;i<list.size();i++)
            result[i] = list.get(i);
        return result;
    }
    
    public TreeNode buildTree(int[] xianxu, int[] zhongxu){
        //双指针 
        int pre = 0;
        int mid = 0;
        //当前节点
        TreeNode curRoot = new TreeNode(xianxu[pre]);
        //root作为根节点 返回
        TreeNode root = curRoot;
        Stack<TreeNode> stack = new Stack<>();
        //入栈
        stack.push(curRoot);
        pre++;
        while(pre < xianxu.length){
            //当前节点 = 中序遍历的节点时候，证明下一个节点是右子树的节点
            if(curRoot.val == zhongxu[mid]){
                //出栈 与中序遍历匹配 不匹配时证明先序遍历的值是当前节点的右节点 
                while(!stack.isEmpty() && stack.peek().val == zhongxu[mid]){
                    curRoot = stack.pop();
                    //mid同步，更新到下一个右节点判断
                    mid++;
                }
                //设置右节点
                curRoot.right = new TreeNode(xianxu[pre]);
                //更新节点
                curRoot = curRoot.right;
                //入栈
                stack.push(curRoot);
                pre++;
            }else{
                //设置左节点
                curRoot.left = new TreeNode(xianxu[pre]);
                curRoot = curRoot.left;
                stack.push(curRoot);
                pre++;
            }
        }
        return root;
    }
}

Newman616

学习了，感谢帖主分享