Share my 13-line(BFS) and 11-line(DFS) Java code with brief explanations


  • 0
    M

    BFS -- Level-order traversal. The target sequence contains the value of each level's last tree node, from top to bottom.

    public class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            Deque<TreeNode> q = new ArrayDeque<>();
            if (root!=null) { q.addLast(root); }
            int curSize = 1, nextSize = 0;
            for (curSize=1; !q.isEmpty(); curSize=nextSize, nextSize=0) {
                for (int i=0; i<curSize; ++i) {  // there are curSize nodes of current level to be dequeued
                    TreeNode head = q.removeFirst();
                    if (i == curSize-1) { ans.add(head.val); }  // add the value of the last node of current level to answer list
                    if (head.left != null) { q.addLast(head.left); ++nextSize; }
                    if (head.right != null) { q.addLast(head.right); ++nextSize; }
                }
            }
            return ans;
        }
    }
    

    DFS -- Preorder traversal, while keep updating the latest tree node value visited for each certain level.

    public class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            preOrder(root, 0, ans);
            return ans;
        }
        
        private void preOrder(TreeNode root, int curLevel, List<Integer> ans) {
            if (root == null) { return; }
            if (curLevel == ans.size()) { ans.add(root.val); }
            else { ans.set(curLevel, root.val); }
            preOrder(root.left, curLevel+1, ans);
            preOrder(root.right, curLevel+1, ans);
        }
    }

Log in to reply
 

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