树问题【Leetcode 96异构树的个数/98验证二叉搜索树/100相同的树/101判断对称/102层序遍历】

前言

树形问题很简单，十有八九靠递归

96. 不同的二叉搜索树（卡特兰数）（medium）

1 <= n <= 19

偶尔面向测试用例编程。

class Solution {
    int ans[20] = {1,       1,        2,         5,         14,
                   42,      132,      429,       1430,      4862,
                   16796,   58786,    208012,    742900,    2674440,
                   9694845, 35357670, 129644790, 477638700, 1767263190};

public:
    int numTrees(int n) { return ans[n]; }
};

98. 验证二叉搜索树（medium）

class Solution {
    long long lastnum = (long long)INT_MIN - 1;
public:
    bool isValidBST(TreeNode* root) {
        bool ans = true;
        if (root == NULL)
            return true;
        if (root->left)
            ans = isValidBST(root->left);
        if (root->val <= lastnum)
            return false;
        
        lastnum = root->val;
        if (ans && root->right)
            ans = ans && isValidBST(root->right);

        return ans;
    }
};

100. 一模一样的二叉树（easy）

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) return true;
        else if (p == NULL || q == NULL) return false;
        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

101. 对称二叉树（easy）

class Solution {
    bool isS(TreeNode*p, TreeNode*q)
    {
        if (p == NULL && q == NULL) return true;
        if (p == NULL || q == NULL) return false;

        return p->val == q->val && isS(p->left, q->right) && isS(p->right, q->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return isS(root->left, root->right);
        
    }
};

102. 层序遍历（medium）

本题额外的要求是区分出层次。看到层序遍历就想到用queue。题解里说的bfs其实是一个东西。但是下面这个代码却很慢。

class Solution {
    const int inf = 2000;
    TreeNode * q[6100];
    int front = 0, tail = 0;
    vector<vector<int>> ans;
    TreeNode * split = new TreeNode(inf);
public:
    vector<vector<int>> levelOrder(TreeNode* root) {

        q[tail++] = root;
        q[tail++] = split;
        vector<int> currGroup;
        while (front != tail)
        {
            // 出队
            TreeNode* curr = q[front++];
            // 如果发现该数是当前组的最后一个，那么它的左右孩子进栈之后，在队列中加入分隔符
            if (curr != NULL)
            {
                currGroup.push_back(curr->val);
                q[tail++] = curr->left;
                q[tail++] = curr->right;
            }
            if (q[front] == split)
            {
                front++;
                q[tail++] = split;
                ans.push_back(currGroup);
                currGroup.clear();
            }
        }
        ans.pop_back();
        return ans;
    }
};

有的时候，明明是一模一样的思路and类似的代码结构，但是运行速度完全不同。有人可能会觉得测评机不讲道理，但其实找出细微差别究竟在哪也是一种乐趣，把代码优化到100%也是很有意思的。

自己写的queue就一个好处——能随机访问，所以，这次我们一次处理一层的节点。

class Solution {
    TreeNode* q[4100];
    int front = 0, tail = 0;
    vector<vector<int>> ans;

public:
    vector<vector<int>> levelOrder(TreeNode* root) {

        q[tail++] = root;

        while (front != tail) {
            // 出队
            vector<int> currGroup;
            int old_tail = tail;
            for (int i = front; i < old_tail; i++) {
                if (q[i] != NULL) {
                    currGroup.push_back(q[i]->val);
                    q[tail++] = q[i]->left;
                    q[tail++] = q[i]->right;
                }
            }
            ans.push_back(currGroup);
            front = old_tail;
        }
        ans.pop_back();
        return ans;
    }
};

amazing