513. 找树左下角的值

题目链接

解：层序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct queue {
    int front, back;
    struct TreeNode *array[10000];
};

int findBottomLeftValue(struct TreeNode* root) {
    struct queue *que = (struct queue *)malloc(sizeof(*que));
    struct TreeNode *node = root;
    int ret = 0;

    memset(que, 0, sizeof(*que));
    que->front = que->back = 0;

    if (root == NULL) {
        return ret;
    }

    que->array[que->back++] = node;

    while (que->front != que->back) {
        int tmp = que->back;
        ret = que->array[que->front]->val;
        while (que->front != tmp) {
            node = que->array[que->front];
            if (node->left != NULL) que->array[que->back++] = node->left;
            if (node->right != NULL) que->array[que->back++] = node->right;
            que->front++;
        }
    }

    return ret;
}

112. 路径总和

题目链接

解: 递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool pathsum(struct TreeNode *node, int target) {
    if (node == NULL) return false;
    if (node->left == NULL && node->right == NULL && node->val == target) {
        return true;
    }

    bool left = pathsum(node->left, target - node->val);
    bool right = pathsum(node->right, target - node->val);

    return left | right;
}

bool hasPathSum(struct TreeNode* root, int targetSum) {
    return pathsum(root, targetSum);
}

解：迭代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct stacknode {
    struct TreeNode *node;
    int sum;
};

struct stack {
    int top;
    struct stacknode stacknode[1000];
};

void push(struct stack *st, struct TreeNode *node, int sum) {
    if (st->top == 99) {
        printf("stack overflow\n");
        exit(1);
    }

    st->stacknode[++st->top].node = node;
    st->stacknode[st->top].sum = sum;
}

struct stacknode pop(struct stack *st) {
    return st->stacknode[st->top--];
}

bool hasPathSum(struct TreeNode* root, int targetSum) {
    struct stack *st = (struct stack *)malloc(sizeof(*st));
    struct TreeNode *node = root;

    memset(st, 0, sizeof(*st));
    st->top = -1;

    if (root == NULL) return false;

    push(st, node, node->val);

    while (st->top != -1) {
        struct stacknode cur = pop(st);
        node = cur.node;

        if (node->right != NULL) {
            push(st, node->right, cur.sum + node->right->val);
        }

        if (node->left != NULL) {
            push(st, node->left, cur.sum + node->left->val);
        }

        if (node->left == NULL && node->right == NULL) {
            if (cur.sum == targetSum) return true;
        }
        
    }

    return false;
}

106. 从中序与后序遍历序列构造二叉树

题目链接

解: 递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode *build_tree(int *inorder, int instart, int inend, int *postorder, int poststart, int postend) {
    if (instart > inend || poststart > postend) {
        return NULL;
    }

    int rootvalue = postorder[postend];
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = rootvalue;
    root->left = NULL;
    root->right = NULL;

    int rootidx;
    for (rootidx = instart; rootidx <= inend; rootidx++) {
        if (inorder[rootidx] == rootvalue) {
            break;
        }
    }

	// rootidx-1-instart 表示前序有多少个元素, 后序就有多少个元素
    root->left = build_tree(inorder, instart, rootidx-1, postorder, poststart, poststart+rootidx-1-instart);
    root->right = build_tree(inorder, rootidx+1, inend, postorder, poststart+rootidx-instart, postend-1);

    return root;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    if (inorderSize <= 0 || postorderSize <= 0) {
        return NULL;
    }

    return build_tree(inorder, 0, inorderSize-1, postorder, 0, postorderSize-1);
}