LeetCode 199.두 갈래 나무의 오른쪽 보기

LeetCode 199.두 갈래 나무의 오른쪽 보기

제목 설명: 두 갈래 나무를 정하고 오른쪽에 서 있는 것을 상상하고 꼭대기에서 끝까지 순서대로 오른쪽에서 볼 수 있는 노드 값을 되돌려줍니다.
예:
입력: [1, 2, 3, null, 5, null, 4] 출력: [1, 3, 4] 설명:

   1                    	    

출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/binary-tree-right-side-view저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.
문제 풀이 사고방식

	BFS: ， ， 。
	DFS:   ---> ---> ， ， ， 。

코드

BFS:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        List<Integer> arr=new ArrayList<>();
        if(root==null) {
            return new ArrayList<Integer>();
        }
        queue.add(root); // 
        while(!queue.isEmpty()){
         
            int len=queue.size();// 
           for(int i=0;i<len;i++){// 
            TreeNode treeNode=queue.poll();// 

            if(i==len-1){
                arr.add(treeNode.val);// 
            }

            if(treeNode.left!=null){
                queue.add(treeNode.left);// 
            }

            if(treeNode.right!=null){
                queue.add(treeNode.right);// 
            }
         }
        }
        return arr;
    }
}

DFS:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	 List<Integer> res=new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root,0);                   // 
        return res;
    }
    public void dfs(TreeNode node,int depth){
        if(node==null){
            return;
        }
        if(depth==res.size()){      // ， ， 
            res.add(node.val);
        }
        depth++;
        dfs(node.right,depth);         // 
        dfs(node.left,depth);           // 
    }
}

태그: BFS, DFS