二叉树的递归算法

将二叉树常见的递归算法罗列如下：

（一）前序/中序/后序遍历

以中序为例：

void inorder(Node* root){ //从根节点的指针开始 
    if(root!=NULL){
        inorder(root->left);
        cout<data<<" ";
        inorder(root->right);
    }
}

（二）求二叉树的高度

int maxDepth(Node* root) {//递归查找
        Node* p=root;
        if(p==NULL) return 0;
        int m=maxDepth(p->left);
        int n=maxDepth(p->right);
        int x=m>n? m+1:n+1;
        return x;
}

（三）求二叉树最大的数

int getmax(Node *node){
    if(node==NULL){
        return -1;
    }
    else{
        int m1=getmax(node->left); //左子树最大的数 
        int m2=getmax(node->right);  //右子树最大的数 
        int n=node->data;  //根节点的值 
        int max=n;
        if(m1>n) {
            max=m1;
        } 
        if(m2>n){
            max=m2;
        }
        return max;
    }
}

（四）求所有最左边叶子结点的和

int sumOfLeftLeaves(TreeNode* root) {
        if(root==NULL) return 0;
        int sum=0; //必须有
        if(root->left){
            if(root->left->left==NULL&&root->left->right==NULL)       //叶子结点
            sum+=root->left->val;
        }
        return sum+sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);  
}

（五）交换——交换左右子树

要求：

思想：后序遍历实现，从下往上，首先交换b结点左孩子的左右子树，然后交换b结点右孩子的左右子树，最后交换b结点的左右子树。（后序遍历思想）

void swap(Node* root){
    if(root){
        swap(root->left);
        swap(root->right);
        Node* temp=root->left;
        root->left=root->right;
        root->right=temp;
    }
}

先序遍历实现，从上到下

Node* invertTree(Node* root) {
        Node* p=root;
        if(p!=NULL) {         
        Node* temp=p->left;
        p->left=p->right;
        p->right=temp;
        invertTree(p->left);  
        invertTree(p->right);}
        return root;
}

（六）计算双支结点(度为2)结点的个数

int Sumnode(Node* root){
    Node* p=root;
    if(p){
        if(p->left&&p->right){
            return Sumnode(p->left)+Sumnode(p->right)+1;  //左+右+根节点 
        }
        else{
            return Sumnode(p->left)+Sumnode(p->right);  //左加右 
        }
    }
}

（七）判断两个二叉树是否相同

　　三种情况：

　　1）两棵树都是空树，则相同

　　2）一个树空，一个树不空，则不同

　　3）两个树非空，比较结点的值

bool isSameTree(TreeNode* p, TreeNode* q) {
        //可能出现的三种情况，注意是两棵树，即两个参数
        if(p==NULL&&q==NULL) return true;
        if(p==NULL||q==NULL) return false;
        if(p->val!=q->val) return false;
        return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    }

（八）合并两棵二叉树

　　法一：改变输入树的结构，即在树1身上改动，返回树1

Node* merge(Node* root1,Node* root2){
    if(root1==NULL) return root2;
    if(root2==NULL) return root1;
    root1->data += root2->data;
    root1->left=merge(root1->left,root2->left);
    root1->right=merge(root1->right,root2->right);
    return root1;
}

　　法二：不改变输入树的结构，新建一个树，返回新树

Node* merge(Node* root1,Node* root2){
    if(root1==NULL) return root2;
    if(root2==NULL) return root1;
    //重新定义一个新的结点
    Node* root=new Node(0); 
    root->data= root1->data + root2->data;
    root->left=merge(root1->left,root2->left);
    root->right=merge(root1->right,root2->right);
    return root;
}

未完待续...

数据结构考研专题

二叉树的递归算法

相关

标签