二叉树的右视图

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

示例:

输入: [1,2,3,null,5,null,4]

输出: [1, 3, 4]

解释:

   1            <---

 /   \

2     3         <---

 \     \

  5     4       <---

左视图

用 size 记录当层的结点数，循环访问时用 child 记录下一层的结点数，当 i = 0 时，是当层第一个结点。

public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    TreeNode node1 = new TreeNode(2);
    TreeNode node2 = new TreeNode(3);
    TreeNode node3 = new TreeNode(5);
    TreeNode node4 = new TreeNode(4);
    root.left =  node1;
    root.right =  node2;
    node1.right = node3;
    node2.right = node4;
    LeftView(root);
}

public static void LeftView(TreeNode node) {
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(node);
    //设置 size 和 child 两个标记，child在循环中会变，size不会变，作为循环条件
    //第一层只有根节点1个，所以size = 1
    int size = 1;
    //记录孩子数
    int child;
    while (!queue.isEmpty()) {
        //初始化孩子数为 0
        child = 0;
        for (int i = 0; i < size; i++) {
            TreeNode node1 = queue.poll();
            // i = 0,说明是该层第一个结点
            if (i == 0) {
                System.out.println(node1.val);
            }
            if (node1.left != null) {
                queue.offer(node1.left);
                child++;
            }
            if (node1.right != null) {
                queue.offer(node1.right);
                child++;
            }
        }
        size = child;
    }
}

右视图

代码1

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Auther: liuhaidong
 * Data: 2019/10/18 0018、21:00
 * Description:
 * @version: 1.0
 */
public class RightView {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(4);
        root.left =  node1;
        root.right =  node2;
        node1.right = node3;
        node2.right = node4;
        RightView(root);
    }

    public static List<Integer> RightView(TreeNode node) {
        List<Integer> returnlist = new ArrayList<>();
        if(node == null){
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(node);
        //设置 size 和 child 两个标记，child在循环中会变，size不会变，作为循环条件
        //第一层只有根节点1个，所以size = 1
        int size = 1;
        //记录孩子数
        int child;
        while (!queue.isEmpty()) {
            //初始化孩子数为 0
            child = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node1 = queue.poll();
                // i = 0,说明是该层第一个结点
                if (i == size-1) {
                    System.out.println(node1.val);
                }
                if (node1.left != null) {
                    queue.offer(node1.left);
                    child++;
                }
                if (node1.right != null) {
                    queue.offer(node1.right);
                    child++;
                }
            }
            size = child;
        }
        return returnlist;
    }
}

代码2

public class Test2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(4);
        root.left =  node1;
        root.right =  node2;
        node1.right = node3;
        node2.right = node4;
        rightSideView(root);
    }
    public static List<Integer> rightSideView(TreeNode root) {
        /*
        思路：使用一个Queue，初始化只有根节点，当Queue有元素时，弹出队列中的元素，设置变量count，记录弹出的元素个数，当达到开始队列个数时说明是队列最后
        一个节点那么可以看到，并且将弹出的节点的左右子节点添加到队列中
         */
        List<Integer> res=new ArrayList<>();
        if (root==null)
        {
            return res;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while (queue.size()>0)
        {
            int count=0;
            int size=queue.size();
            while (queue.size()>0)
            {
                TreeNode node=((LinkedList<TreeNode>) queue).pop();
                if (node.left!=null)
                {
                    queue.add(node.left);
                }
                if (node.right!=null)
                {
                    queue.add(node.right);
                }
                count++;
                if (count==size)
                {
                    res.add(node.val);
                    break;
                }
            }
        }
        return res;
    }
}

代码3

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res=new ArrayList<>();
    if(root==null) {
        return res;
    }
    Queue<TreeNode> queue=new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int cnt=queue.size();
        while(cnt-->0){
            // y-->0在java中是什莫意思
            // 先比较（y--）是否大于0，再让y=y-1，
            // 如果是--y>0,就是先让y=y-1,再比较现在的y值是否大于0
            TreeNode node=queue.poll();
            if(node.left!=null) {
                queue.offer(node.left);
            }
            if(node.right!=null) {
                queue.offer(node.right);
            }
            if(cnt==0) {
                res.add(node.val);
            }
        }
    }

    return res;
}