Subject to introduce

Force buckle 199: leetcode-cn.com/problems/bi…

Method 1: BFS or sequence traversal

Refer to the sequence traversal logic in [102. Sequence traversal of binary trees], that is, sequence traversal of each layer, and then take out the last element of each layer and add it to the result set.

The code is as follows:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {

    public List<Integer> rightSideView(TreeNode root) { 
        if(root == null) {
            return new ArrayList<Integer>();
        }
        return levelOrder(root);
    }

    // Order traversal of binary tree
    public List<Integer> levelOrder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root ! =null) {
            queue.add(root);
        }
        while(! queue.isEmpty()) {int n = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < n; i++) { 
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left ! =null) {
                    queue.add(node.left);
                }
                if(node.right ! =null) {
                    queue.add(node.right);
                }
            }
            result.add(level.get(level.size() -1));
        }
        returnresult; }}Copy the code

Method 2: DFS

The order of root -> right subtree -> left subtree ensures that each layer is the first to access the rightmost node. (As opposed to “root -> left subtree -> right subtree”, the left-most node is visited first at each level.)

The code is as follows:

class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0); // Access starts from the root node, whose depth is 0
        return res;
    }

    private void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        // First access the current node, then recursively access the right and left subtrees.
        if (depth == res.size()) {   // If the depth of the current node is not already in the RES, the current node is the first node to be accessed at that depth, so add the current node to the RES.res.add(root.val); } depth++; dfs(root.right, depth); dfs(root.left, depth); }}Copy the code