Java描述 LeetCode，199. Binary Tree Right Side View 站在二叉树的右侧 看树

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view

站在右侧看一颗二叉树，等于要输出每一个level最右侧的那个节点。

☘️数处每一个level最右侧的节点，首先想到的是level order traverse算法，也就是层次遍历，只要注意每次到最右边的节点的时候就可以add 进result list中了，利用层次遍历的模版代码，稍加修改就可以达到目的。

public static List rightSideView(TreeNode root) {
    List result = new ArrayList<>();
    Queue queue = new ArrayDeque<>();
    if (root == null) {
        return result;
    }

    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (i == size - 1) {
                result.add(node.val);
            }
        }
    }
    return result;
}

☘️解法2是画了一个完全二叉树，如下：

public class TreeUtils {
    
    public static TreeNode getTree() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        return root;
    }
}

☘️通过之前的先序遍历算法，我们如果改成根右左，就可以得到这样的第一个序列：1 376 254，那么我只需要利用递归求出最大的深度depth，就可以取前depth个数字就可以了。于是，就给出了下面的代码：

public static int recursion(TreeNode root, List result) {
    if (root == null) {
        return 0;
    }
    result.add(root.val);
    int rightLevel = recursion(root.right, result);
    int leftLevel = recursion(root.left, result);
    return Math.max(leftLevel, rightLevel) + 1;
}

public static List rightSideView2(TreeNode root) {
    List result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    int level;
    level = recursion(root, result);
    return result.subList(0, level);
}

☘️过了一大半的测试用例，遇到了这样的测试用例失败了（例子在注释代码中）。问题在哪呢？如果，有一个节点是在左子树上的时候就会失败。

☘️我们用上面的代码，输出一下这个例子的遍历结果，1 3 2 4，我们实际需要的是1 3 4对不对，我们实际上可以记录一个level数组，记录每一个节点所在的层次，这里是level=[1, 2, 2, 3]，我们只需要将每一层第一次出现的节点放进结果当中即可。代码如下：

public static int recursion2(TreeNode root, int level, List result, List levels) {
    if (root == null) {
        return 0;
    }
    result.add(root.val);
    levels.add(level);
    int rightLevel = recursion2(root.right, level + 1, result, levels);
    int leftLevel = recursion2(root.left, level + 1, result, levels);
    return Math.max(leftLevel, rightLevel) + 1;
}


public static List rightSideView3(TreeNode root) {
    List rightView = new ArrayList<>();
    List treeNodes = new ArrayList<>();
    List levels = new ArrayList<>();
    if (root == null) {
        return treeNodes;
    }
    int level = 1;
    int maxLevel = recursion2(root, level, treeNodes, levels);
    System.out.println(treeNodes);
    System.out.println(levels);
    System.out.println(maxLevel);

    int countLevel = 1;
    for (int i = 0; i < levels.size(); i++) {
        if (countLevel > maxLevel) {
            return rightView;
        }
        if (levels.get(i) == countLevel) {
            rightView.add(treeNodes.get(i));
            countLevel++;
        }
    }
    return rightView;
}

☘️第三种解法是将第二种方法用非递归的形式写出来，非递归就是类似于将根右左的非递归程序写出来，同时维护节点栈和节点对应的level栈，并且通过map来记录每一个level第一次出现的节点，如果map中有，就代表不是第一次出现。根据这个思路可以得到下面的代码。

public static List rightSideView4(TreeNode root) {
    Map map = new HashMap<>();
    List rightView = new ArrayList<>();
    Stack nodeStack = new Stack<>();
    Stack levelStack = new Stack<>();

    if (root == null) {
        return rightView;
    }
    int level = 0;
    int maxLevel = -1;

    TreeNode cur = root;
    while (cur != null || !nodeStack.isEmpty()) {
        if (cur != null) {
            level++;
            maxLevel = Math.max(maxLevel, level);
            if (map.get(level) == null) {
                map.put(level, cur);
            }
            nodeStack.push(cur);
            levelStack.push(level);
            cur = cur.right;
        } else {
            cur = nodeStack.pop();
            level = levelStack.pop();
            cur = cur.left;
        }
    }
    System.out.println(map);
    System.out.println(maxLevel);
    for (int i = 1; i <= maxLevel; i++) {
        rightView.add(map.get(i).val);
    }
    return rightView;
}

☘️这里主要是几个小算法的应用

• 层次遍历的非递归形式。
• 先序遍历的递归/非递归。
• 求树的最大深度。

帮俺点赞！要是评论一下就更好了！（贪心算法）