二叉树

二叉树

二叉树的数据结构

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

二叉树的构建

递归

int preorder[100], inorder[100];
int n; // 数据个数

TreeNode *buildTree(int index, int left, int right) {
    if (left > right) {
        return NULL;
    }
    TreeNode *root = new TreeNode(preorder[index]);
    int root_index = 0;
    // 找到inorder中根节点位置
    for (int i = 0; i < n; i++) {
        if (inorder[i] == preorder[index]) {
            root_index = i;
            break;
        }
    }
    int left_tree_size = root_index - left;
    root->left = buildTree(index + 1, left, root_index - 1);
    root->right = buildTree(index + left_tree_size + 1, root_index + 1, right);
    return root;
}
TreeNode *buildTree() {
    return buildTree(0, 0, n - 1);
}

循环

TreeNode *buildTreeByStack() {
    TreeNode* q[100];
    int top = 0;
    TreeNode *root = new TreeNode(preorder[0]);
    q[++top] = root;
    int inorder_index = 0;
    for (int i = 1; i < n; i++) {
        TreeNode *node = q[top];
        if (node->val != inorder[inorder_index]) {
            TreeNode *tmp = new TreeNode(preorder[i]);
            node->left = tmp;
            q[++top] = tmp;
        } else {
            while (top > 0 && q[top]->val == inorder[inorder_index]) {
                node = q[top];
                --top, ++inorder_index;
            }
            TreeNode *tmp = new TreeNode(preorder[i]);
            node->right = tmp;
            q[++top] = tmp;
        }
    }
    return root;
}

二叉树的遍历

递归

void preOrder(TreeNode *node) {
    if (!node)
        return;
    printf("%d ", node->val);
    preOrder(node->left);
    preOrder(node->right);
}

循环

原理

记当前节点为cur

• 当cur的左子节点不存在时，cur向右移动

• 当cur的左子节点存在，找到cur左子树上最右的节点，记为mostright

• 如果mostright的右子节点为空，则将右子节点指向cur，cur继续向左移动

• 如果mostright的右子节点不为空，则将右子节点指向null，cur向右移动

对于没有左子树的节点只会走一次，有左子树的节点会走两次

时间复杂度为O(n)，空间复杂度为O(1)

void mirrorPreorder(TreeNode *node) {
    TreeNode *cur = node;
    while (cur) {
        TreeNode *mostRight = cur->left;
        if (mostRight) {
            while (mostRight->right && mostRight->right != cur) {
                mostRight = mostRight->right;
            }
            if (!mostRight->right) {
                mostRight->right = cur;
                printf("%d ", cur->val);
                cur = cur->left;
                continue;
            } else {
                mostRight->right = NULL;
            }
        } else {
            printf("%d ", cur->val);
        }
        cur = cur->right;
    }
}