本文共 1785 字，大约阅读时间需要 5 分钟。

链接：

大意：

给定一棵树的根节点root，假设你站在树的最右边，要求找出你所能看到的节点（从上往下）。例子：

思路：

层次遍历，取每层的最右节点即可。

代码：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public List
   
     rightSideView(TreeNode root) {        List
    
      res = new ArrayList<>();        if (root == null)            return res;        LinkedList
     
       queue = new LinkedList<>();        queue.add(root);        TreeNode ll = root, l = root;        while (!queue.isEmpty()) {            TreeNode node = queue.pollFirst();            if (node.left != null) {                l = node.left;                queue.addLast(l);            }            if (node.right != null) {                l = node.right;                queue.addLast(l);            }            if (node == ll) {                res.add(ll.val); // 层次遍历 取每层的最右节点                ll = l;            }        }        return res;    }}
     
    
   

结果：

结论：

基础题，但得想想最优解。  

改进：（递归版）

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    int deepestLayer = -1; // 已经走到的最深层    public List
   
     rightSideView(TreeNode root) {        List
    
      res = new ArrayList<>();        myOrder(root, res, 0);        return res;    }    public void myOrder(TreeNode root, List
     
       res, int currLayer) {        if (root == null)            return ;        if (currLayer > deepestLayer) {            deepestLayer = currLayer; // 每当走到一个比deepestLayer还深的层时  更新deepestLayer            res.add(root.val);        }        myOrder(root.right, res, currLayer + 1);        myOrder(root.left, res, currLayer + 1);    }}
     
    
   

转载地址：http://uaesi.baihongyu.com/