By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、二叉树的右视图

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

示例:

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

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

1.1、解题思路

层序遍历

1.2、算法

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null){
        return res;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()){
        int size = queue.size();
        int val = 0 ;
        while (size > 0){
            size--;
            TreeNode node = queue.remove();
            val = node.val;

            //先来左节点，最后肯定留下的是右节点
            if (node.left != null){
                queue.add(node.left);
            }

            if (node.right != null){
                queue.add(node.right);
            }
        }
        res.add(val);
    }
    return res;
}

1.3、测试

@Test
public void test(){
    System.out.println(rightSideView(initTreeNode()));
}


public TreeNode initTreeNode(){
    TreeNode treeNode5 = new TreeNode(5, null ,null);
    TreeNode treeNode4 = new TreeNode(4, null , null);
    TreeNode treeNode3 = new TreeNode(3, null, treeNode4);
    TreeNode treeNode2 = new TreeNode(2, null, treeNode5);
    TreeNode root1 = new TreeNode(1, treeNode2, treeNode3);
    return root1 ;
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
    TreeNode(int x, TreeNode left, TreeNode right) {
        this.val = x;
        this.left = left;
        this.right = right;

    }
}

​

ContactAuthor