二叉树-二叉树的右视图

二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

输入：二叉树的根结点
输出：整型列表
思路：使用层序遍历，建立二元列表，每一层列表的最后一个元素即为最右边的结点

二叉树层序遍历
使用递归方式:

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        method01(root, 0);
        return result;
    }
    public void method01(TreeNode root, int deep){
        if(root == null){
            return;
        }
        deep++;
        if(result.size() < deep){
            List<Integer> temp = new ArrayList<>();
            result.add(temp);
        }
        result.get(deep - 1).add(root.val);
        method01(root.left, deep);
        method01(root.right, deep);
    }
}

层序遍历
使用迭代和队列

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        //使用队列
        method02(root);
        return result;
    }
    public void method02(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> que = new LinkedList<>();
        //将头结点加入队列
        que.offer(root);
        while(!que.isEmpty()){
            //新建列表
            List<Integer> temp = new ArrayList<>();
            int len = que.size();
            while(len > 0){
                TreeNode tmpNode = que.poll();
                temp.add(tmpNode.val);
                len--;
                if(tmpNode.left != null){
                    que.offer(tmpNode.left);
                }
                if(tmpNode.right != null){
                    que.offer(tmpNode.right);
                }
            }
            result.add(temp);
        }
    }
}

然后本题也就是使用层序遍历，并返回每一层最后一个结点

class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        method(root);
        return result;
    }
    public void method(TreeNode root){
        if(root == null){
            return;
        }
        //定义队列
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int len = que.size();
            while(len > 0){
                TreeNode tmpNode = que.poll();
                if(len == 1){
                    result.add(tmpNode.val);
                }
                len--;
                if(tmpNode.left != null){
                    que.offer(tmpNode.left);
                }
                if(tmpNode.right != null){
                    que.offer(tmpNode.right);
                }
            }
        }
    }
}