二叉树

22

void pre(Node *root){
    if(root == NULL){
        return;
    }
    cout << root -> val << endl;
    pre(root->left);
    pre(root->right);
}

void mid(Node *root){
    if(root == NULL){
        return;
    }
    mid(root->left);
    cout << root -> val << endl;
    mid(root->right);
}

void lst(Node *root){
    if(root == NULL){
        return;
    }
    lst(root->left);
    lst(root->right);
    cout << root -> val << endl;
}

计算二叉树深度
先计算左右子树的深度，然后整棵树的深度就是左右子树深度较大值加1（当前节点）

int caculDepth(Node *root){
    if(root == NULL){
        return 0;
    }
    return max(caculDepth(root->left), caculDepth(root->right)) +1;
}

镜像二叉树

23.png

void Mirror(TreeNode *pRoot) {
    if(pRoot == NULL) return;
    Mirror(pRoot->left);
    Mirror(pRoot->right);
    swap(pRoot->left, pRoot->right);
}

从上往下打印出二叉树的每个节点，同层节点从左至右打印.
利用广度优先搜索思想。

vector<int> PrintFromTopToBottom(TreeNode* root) {
    queue<TreeNode*> q;
    vector<int> v;
    if(root == NULL) return v;
    q.push(root);
    while(!q.empty()){
        TreeNode* node = q.front();
        q.pop();
        v.push_back(node->val);
        if(node->left != NULL){
            q.push(node->left);
        }
        if(node->right != NULL){
            q.push(node->right);
        }
    }
    return v;
}