构造完全二叉树

#include <iostream>
#include <stack>
#include <vector>
#include <queue>
using namespace std;

void assert(bool cond)
{
    cout << (cond ? "Pass" : "Fail") << endl;
}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& tree)
    {
        TreeNode* root = nullptr;
        if (tree.size() < 1 || tree[0] == -1) {
            return root;
        }
        queue<TreeNode*> q;
        root = new TreeNode(tree[0]);
        q.push(root);
        size_t i = 1;
        while (!q.empty() && i < tree.size()) {
            TreeNode* node = q.front();
            q.pop();
            if (tree[i] != -1) {
                node->left = new TreeNode(tree[i]);
                q.push(node->left);
            }
            ++i;

            if (tree[i] != -1) {
                node->right = new TreeNode(tree[i]);
                q.push(node->right);
            }
            ++i;
        }

        //printTree(root);
        //cout << endl;

        return root;
    }

    void printTree(TreeNode* node)
    {
        if (node == nullptr) {
            return;
        }
        cout << node->val << " -> ";
        printTree(node->left);
        printTree(node->right);
    }

    bool isSymmetric(TreeNode* root)
    {
        return false;
    }

    Solution()
    {
        test1();
        test2();
    }

    void test1()
    {
        vector<int> tree = { 1,2,2,3,4,4,3 };
        bool expect = true;
        TreeNode* root = nullptr;
        root = buildTree(tree);
        bool ret = isSymmetric(root);
        assert(expect == ret);
    }

    void test2()
    {
        vector<int> tree = { 1,2,2,-1,3,-1,3 };
        bool expect = false;
        TreeNode* root = nullptr;
        root = buildTree(tree);
        bool ret = isSymmetric(root);
        assert(expect == ret);
    }
};

int main()
{
    Solution solu;
    return 0;
}

  

上一篇:在/bin/bash中使expect off


下一篇:浅析CompareAndSet(CAS)