199. Binary Tree Right Side View

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 <—
/ \
2 3 <—
\ \
5 4 maxDepth,则将该节点的值加入到结果中,并且更新maxDepth。 注意:我们每次都是先遍历右子树
我们也可以从level-order traversal来解这道题目,来取每层的最后一个节点。

DFS:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int maxDepth = 0;
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        helper(root, 1, res);
        return res;
    }

    public void helper(TreeNode root, int depth, List<Integer> res) {
        if (maxDepth < depth) {
            maxDepth = depth;
            res.add(root.val);
        }
        if (root.right != null) 
            helper(root.right, depth + 1, res);
        if (root.left != null) 
            helper(root.left, depth + 1, res);
    }
}

Level-order traversal:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
         List<Integer> res = new ArrayList<>();
         if (root == null) return res;
         ArrayDeque<TreeNode> queue = new ArrayDeque<>();
         queue.offer(root);
         while (!queue.isEmpty()) {
             int count = queue.size();
             for (int i = 0; i < count; i++) {
                 if (i == count - 1) { // the last element in level
                    res.add(queue.peek().val);
                 }
                 TreeNode node = queue.poll();
                 if (node.left != null) queue.offer(node.left);
                 if (node.right != null) queue.offer(node.right);
             }
         }

         return res;

    }
}
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