Leetcode 199.二叉树的右视图【C++】

地址：https://leetcode-cn.com/problems/binary-tree-right-side-view/

题目

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

解题思路

首先这是一个很明显的使用递归算法的题目，由于是“右视图”，所以应该采用后序遍历，先遍历右子女结点，再遍历左子女结点。

二叉树的递归遍历是不难实现的，但是这个题要找的是从右侧能看到的结点，以上述示例为例，显然能看到的结点就是右侧的三个结点 [1, 3, 4] 。假设结点 5 还有一个左孩子结点值为 6 ，那么在结点 6 的右侧是没有任何结点阻挡的，所以 6 也应该能看到。

不难发现，具体能看到的结点并不一定只是最右侧一条路径上的的所有结点，而是跟 深度 有关。如果左子树存在深度更深的结点，那就也可以被看到。

在函数外部定义一个 depth 用于记录当前遍历过的所有路径所达到的最深的深度，换言之如果遇到大于 depth 的结点，那么这个结点就是可以被看到的。在调用递归函数前，需要确保传入的是非空结点，当然也可以在递归函数内部判断当前结点是否为空。

递归函数有三个参数，vector<int>& nodes 用于保存返回值，注意必须是引用，这样才能始终在一个数组上更新找到的结点；TreeNode* cur 即传入的非空结点，将其作为新的树根；int dp 即实际的深度，用于和最大到达深度 depth 做对比。

代码

/**
 * 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 {
    int depth = 0;//遍历到的最大深度
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> nodes;
        //调用递归函数前确保传入非空结点
        if (root != NULL) {
            backtrack(nodes, root, 1);
        }
        return nodes;
    }

    void backtrack(vector<int>& nodes, TreeNode* cur, int dp) {
        //当前深度大于最大遍历深度
        if (dp > depth) {
            depth = dp;//更新最大深度
            nodes.push_back(cur->val);//添加可见结点
        }
        //结束条件：没有子女节点
        if (cur->right == NULL && cur->left == NULL) {
            return;
        }
        //选择右侧
        if (cur->right != NULL) {
            backtrack(nodes, cur->right, dp + 1);
        }
        //右侧为空则选择左侧
        if (cur->left != NULL) {
            backtrack(nodes, cur->left, dp + 1);
        }
    }
};