LeetCode - 199. Binary Tree Right Side View

Category: Algorithm
Difficulty: Medium
Tags: Tree, Depth-first Search, Btradth-first Search
Discription: https://leetcode.com/problems/binary-tree-right-side-view/#/description

本題要我們依序取得二元樹中各層最右邊的元素，演算法並不難，稍微變化一下前序運算(Pre-Order)便可輕易實作出來：

1. 用遞迴的方式，從根節點向下走訪。依前序運算之順序：根、右子樹、左子樹，確保走訪順序會先經過各層最右邊之元素，再以一變數紀錄走訪深度。
2. 若走訪深度與現結果陣列之元素數量相同，便將此節點之元素推入結果陣列之中。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> results;
        selectRight(root, 0, &results);
        return results;
    }
    void selectRight(TreeNode* curNode, int curDepth, vector<int>* results){
        if(curNode==NULL)
            return;
        if(curDepth==(*results).size())
            (*results).push_back(curNode->val);
        selectRight(curNode->right, curDepth+1, results);
        selectRight(curNode->left, curDepth+1, results);
    }
};
以上述二條件篩選下來，便可依序得出各層之最右邊元素。