Binary Tree Right Side View

Leave a comment

November 22, 2016 by oneOokay

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

1

You should return [1, 3, 4].


其实就是求一棵树的每一层的最右一个点.

总体来说有两种方法:BFS和DFS。

我的想法是BFS的一种:其实就是层遍历,求每一层的最右的那个node,从上到下放到一个list里面。

public class Solution {
    public List rightSideView(TreeNode root) {
        List ans = new ArrayList();
        if (root == null){
            return ans;
        }
        
        Queue queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()){
            int count = queue.size();
            while (count > 0){
                count --;
                TreeNode node = queue.poll();
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
                if (count == 0){
                    ans.add(node.val);        
                }
            }
        }
        return ans;
    }
}

DFS:类似于LevelOrderTraversal level III 的DFS

  1. 每个深度只取最右的一个点加入
  2. 加入ans的条件是:当深度和ans.size()相等的时候
public class Solution {
    public List rightSideView(TreeNode root) {
        List ans = new ArrayList();
        if (root == null){
            return ans;
        }
        
        dfs(root, ans, 0); //深度为0,ans.size()为0.
        return ans;
    }
    
    private void dfs(TreeNode node, List ans, int depth){
        if (node == null){
            return;
        }
        
        if (depth == ans.size()){ //当两者相等的时候,ans里面加入一个node
//此时ans.size()就比depth多1了。那么在下一步的dfs中,深度加一,这样两者相等了。
就会把遇见的第一个右儿子加到ans里面去。
            ans.add(node.val);
        }
        if (node.right != null){//永远都是先右儿子,因为要得到right view
            dfs(node.right, ans, depth + 1);//这里是不断向右走的一个递归
        }
//这里node.right的dfs结束之后,继续处理node.left的dfs。此时的ans已经发生了变化,加入
了其他的相应depth的点;而这里的depth却还是跟同层的node.right的一样。所以在往左的dfs中,
一直等到depth重新等于ans.size()的时候,才会往里面加。
        if (node.left != null){
            dfs(node.left, ans, depth + 1);
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: