#LeetCode# 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       <---

You should return [1, 3, 4].

这道题值得反复回味，两种解法，一种迭代，一种递归。

迭代解法，层序遍历，

/**

 * 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> ret = new ArrayList<Integer>();

        if(root == null) return ret;

        Queue<TreeNode> q = new LinkedList<TreeNode>();

        q.offer(root);

        while(!q.isEmpty()) {

            int cnt = q.size();

            for(int i = 0; i < cnt; i++) {

                TreeNode cur = q.poll();

                if(i == cnt-1) {

                    ret.add(cur.val);

                }

                if(cur.left != null) {

                    q.offer(cur.left);

                }

                if(cur.right != null) {

                    q.offer(cur.right);

                }

            }

        }

        return ret;

    }

}

递归解法，

/**

 * 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> ret = new ArrayList<Integer>();

        if(root == null) return ret;

        int level = 1;

        helper(root, level, ret);

        return ret;

        

    }

    

    public void helper(TreeNode root, int level, List<Integer> ret) {

        if(root == null) 

            return;

        if(level > ret.size()) {

            ret.add(root.val);

        }

        

        helper(root.right, level + 1, ret);

        helper(root.left, level + 1, ret);

        

    }

}

这里注意，递归调用helper的次序，先遍历root.right，再遍历root.left。巧妙地运用level来控制ret取到每一层的最右结点权值，妙不可言呢！