JAVA Detailed explanation for : BFS + DFS


  • 0
    C
    1. BFS with queue
      Since we want only the right-most node on each level, when forming a queue for certain level, we need firstly add rightChild, and then leftChild.
      For each level manipulation, we only keep record of the 1st element of that level.
    // version 1: bfs with Queue
    class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            // edge case:
            List<Integer> res = new ArrayList<>();
            if( root == null ) return res;
            
            // general case:
            Deque<TreeNode> q = new LinkedList<>();
            q.offer(root);
            
            while( q.size() > 0 ){
                int num = q.size();
                for( int i = 0; i < num; i++ ){
                    TreeNode temp = q.poll();
                    if( i == 0 ) res.add( temp.val );
                    if( temp.right != null ) q.offer( temp.right );
                    if( temp.left  != null ) q.offer( temp.left );
                }
            }
            return res;
        }
    }
    
    1. DFS with hashSet
      we all know DFS could give us an in-order traversal, like: parant -> rightChild -> leftChild.
      So here we do exactly the same thing except we have a Set to help us maintain the current level we have already traversed.
      Each time we do the DFS recursion call, we also give the current level as the 2nd parameter, in order to reject dealing with this node in case a node on this level has already been traversed; OR deal with this node in case there is no record of such level in our Set.
    
    // version 2: dfs
    class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            // edge case:
            List<Integer> res = new ArrayList<>();
            if( root == null ) return res;
            
            // general case:
            HashSet<Integer> s = new HashSet<>(); // to keep track of level, rejecting non-right-most nodes
            DFS( root, s, 0, res);
            return res;
        }
        
        private void DFS( TreeNode root, HashSet<Integer> s, int level, List<Integer> res ){
            
            // base case:
            if( root == null ) return;
            
            // recursive case:
            if( !s.contains(level) ){
                s.add( level );
                res.add( root.val );
            }
            DFS( root.right, s, level+1, res );
            DFS( root.left,  s, level+1, res );
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.