LeetCode:199

Posted on

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root,res,0);
        return res;
    }
    
    public void helper(TreeNode root, List<Integer> res, int level) {
        if(root==null) {return;}
        if(res.size()==level) {res.add(root.val);}
        helper(root.right,res,level+1);
        helper(root.left,res,level+1);
    }
}

考虑到会出现树不平衡的情况:
1
/ \\
2 3
\\
5
所以既要考虑到左边的子树，也要考虑到右边的子树。此例中如果每次递归都只考虑最右边的子树的节点，会发现3没有子节点，这时候就没办法回到2节点了。
这种解法的技巧在于用level来确保每一层只会选取一个节点。先递归右子树再递归左子树则解决了不平衡的问题：如果右子树没了，再考虑同一层的左子树。