545. Boundary of Binary Tree

dfs O(n) time O(logn) space
遍历左半边的时候，相当于

if (lb) {
    res.push_back(root->val);
}
dfs(root->left, lb, false);
dfs(root->right, lb && !root->left, false); // 只有左子不存在才考虑右子

遍历右半边的时候，相当于

dfs(root->left, false, rb && !root->right); // 只有右子不存在才考虑左子
dfs(root->right, false, rb);
if (rb) {
    res.push_back(root->val);
}

/**
 * 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> boundaryOfBinaryTree(TreeNode* root) {
        if (!root) return {};
        res.push_back(root->val);
        dfs(root->left, true, false); // 左右分两半递归遍历，遍历左半边时，右flag永远是false
        dfs(root->right, false, true); // 遍历右半边时，左flag永远是false
        return res;
    }

    void dfs(TreeNode *root, bool lb, bool rb) {
        if (!root) return;
        if (!root->left && !root->right) {
            res.push_back(root->val);
            return; // 所有的叶节点放完即返回
        }
        if (lb) { // 左半边的遍历顺序是中左右
            res.push_back(root->val);
        }
        dfs(root->left, lb, rb && !root->right); // 右半边的内部节点不加，当右子树不为空，左边除叶节点以外所有节点都认为是内部节点
        dfs(root->right, lb && !root->left, rb); // 左半边的内部节点不加，当左子树不为空，右边除叶节点完所有节点都认为是内部节点
        if (rb) { // 右半边的遍历顺序是左右中
            res.push_back(root->val);
        }
    }

    vector<int> res;
};

/**
 * 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> boundaryOfBinaryTree(TreeNode* root) {
        if (!root) return {};
        l.push_back(root->val);
        helperL(root->left, true);
        helperR(root->right, true);
        l.insert(end(l), rbegin(r), rend(r));
        return l;
    }

    void helperL(TreeNode *root, bool border) {
        if (!root) return;
        if (border) {
            l.push_back(root->val);
            helperL(root->left, true);
            helperL(root->right, !root->left);
        } else if (!root->left && !root->right) {
            l.push_back(root->val);
        } else {
            helperL(root->left, border);
            helperL(root->right, border);
        }
    }

    void helperR(TreeNode *root, bool border) {
        if (!root) return;
        if (border) {
            r.push_back(root->val);
            helperR(root->right, true);
            helperR(root->left, !root->right);
        } else if (!root->left && !root->right) {
            r.push_back(root->val);
        } else {
            helperR(root->right, border);
            helperR(root->left, border);
        }
    }

    vector<int> l, r;
};