Simple Stack Solution


  • 0
    public List<Integer> rightSideView(TreeNode root) {
    		List<Integer> l = new ArrayList<Integer>();
    		if(root==null) return l;
    		int maxDepth = 0;
    		Stack<TreeNode> tovisit = new Stack<TreeNode>();
    		Stack<Integer> levels = new Stack<Integer>();
    		tovisit.push(root);
    		levels.push(1);
    		while(!tovisit.empty()) {
    			TreeNode visiting = tovisit.pop();
    			int level = levels.pop();
    			if(level>maxDepth) {
    				l.add(visiting.val);
    				maxDepth=level;
    			}
    			if(visiting.left!=null) {
    				tovisit.push(visiting.left);
    				levels.push(level+1);
    			}
    			if(visiting.right!=null) {
    				tovisit.push(visiting.right);
    				levels.push(level+1);
    			}
    		}
    		return l;
    	}
    
    • This Solution is based on PreOrder traversal, but visiting before
      right subtree, then left subtree.
    • The visit order is root->right->left.
    • While visiting the tree we keep track of the level of the deepest
      node visited.
    • The nodes on the following subtrees will be added to the results only
      if they are deeper than the deepest node visited (a node can be seen
      from a Right Side View only if it is at a deeper level that the
      preceding subtrees).

Log in to reply
 

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