My simple accepted solution(JAVA)


  • 281

    The core idea of this algorithm:

    1.Each depth of the tree only select one node.

    1. View depth is current size of result list.

    Here is the code:

    public class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> result = new ArrayList<Integer>();
            rightView(root, result, 0);
            return result;
        }
        
        public void rightView(TreeNode curr, List<Integer> result, int currDepth){
            if(curr == null){
                return;
            }
            if(currDepth == result.size()){
                result.add(curr.val);
            }
            
            rightView(curr.right, result, currDepth + 1);
            rightView(curr.left, result, currDepth + 1);
            
        }
    }

  • 1
    H

    What is the time complexity?


  • 4

    It should be O(n) time cost where n is the total node of the tree.


  • -2
    S
    This post is deleted!

  • 1
    S

    But this is really elegant and clear code and the algorithm is easy to catch!
    Thanks for sharing!


  • 1

    Thanks a lot!


  • 2

    This algorithm just traverse each node once. So it's time cost should be indeed O(n). I think the point you wanna mention is the space complexity. The algorithm cost (log(n) ~ n) memory space because of the recursion call used.


  • 0
    S

    Great reply! Thanks a lot!


  • 0
    W

    Good ideal! I used bfs method to solve this problem and i think your code is better and more simple


  • 1

    Thank you very much! I'm full of energy now : )


  • 0
    L
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            helper(res, root, 0);
            return res;
        }
    
        public void helper(List<Integer> res, TreeNode root, int level) {
            if(root == null) return;
            if(res.size() == level) 
                res.add(level, root.val);
            helper(res, root.right, level + 1);
            helper(res, root.left, level + 1);
        }
    

    same idea with you, can we do it without recursion??


  • 1

    Use a stack to simulate the process of recursion. I will put the code after your answer.


  • 14

    Using a stack to simulate this algorithm instead of recursion:

    public class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            if(root == null){
                return new ArrayList<Integer>();
            }
            
            List<Integer> result = new ArrayList<Integer>();
            Stack<NodeWithDep> stack = new Stack<NodeWithDep>();
            
            NodeWithDep nwdRoot = new NodeWithDep(root, 0);
            stack.push(nwdRoot);
            while(!stack.isEmpty()){
                NodeWithDep nwd = stack.pop(); 
                TreeNode curr = nwd.node;
                if(nwd.depth == result.size()){
                    result.add(curr.val);
                }
                if(curr.left != null){
                    stack.push(new NodeWithDep(curr.left, nwd.depth + 1));
                }
                if(curr.right != null){
                    stack.push(new NodeWithDep(curr.right, nwd.depth + 1));
                }
            }
            return result;
        }
        
        class NodeWithDep{
            TreeNode node;
            int depth;
            NodeWithDep(TreeNode node, int depth){
                this.node = node;
                this.depth = depth;
            }
        }
        
    }

  • 3

    Great DFS code! Very nice idea of noticing currDepth = result.size() to be the condition to add the node.


  • 0

    The recursive code is much harder. But your code is still very clear :-)


  • 1

    Thanks for your approval !


  • 1

    Again, Thank you !


  • 15

    I don't understand why this answer becomes top 1. The binary level order traversal (i.e., BFS solution) is easier to understand and has the same time/space efficiency.


  • 0
    S
    This post is deleted!

  • 1
    N

    Try something hard to improve skills.


Log in to reply
 

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