29. Right view of binary tree

199. Right side view of binary tree

Given a binary tree The root node root, Imagine yourself on the right side of it , In order from top to bottom , Returns the value of the node as seen from the right .

Example 1:

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

Example 2:

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

Example 3:

 Input : []
 Output : []

BFS Level traversal , Add the last data of each layer to the result

/** * 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) {
    
        List<Integer> res = new ArrayList<Integer>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        if(root==null) return res;
        q.add(root);
        while(!q.isEmpty()){
    
            int n = q.size();
            for(int i=0;i<n;i++){
    
                TreeNode t = q.poll();
                if(t.left!=null) q.add(t.left);
                if(t.right!=null) q.add(t.right);
                if(i==n-1) res.add(t.val);
            }
        }
        return res;

    }
}

DFS

Two 、DFS （ Time 100%）

Ideas ： We are in accordance with the 「 Root node -> Right subtree -> The left subtree 」 Sequential access to , You can ensure that each layer is the first to access the rightmost node .

（ And preorder traversal 「 Root node -> The left subtree -> Right subtree 」 Just the opposite , Go through each layer first, and the leftmost node is the first to be visited ）

Time complexity ： O(N), Each node accesses 1 Time .
Spatial complexity ： O(N), Because this is not a balanced binary tree , The depth of a binary tree is at least logN, In the worst case, it will degenerate into a linked list , Depth is NN, Therefore, the stack space used in recursion is O(N) Of .

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

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

    private void dfs(TreeNode root, int depth) {
    
      		
      	if(root==null){
    
            return;
        }
        //  First visit   Current node , Then recursively access   Right subtree   and   The left subtree .
        if (depth == res.size()) {
       //  If the depth of the current node does not appear in res in , It indicates that the current node is the first accessed node at this depth , So add the current node to res in .
            res.add(root.val);
        }
        depth++;
        dfs(root.right, depth);
        dfs(root.left, depth);
    }
}