当前位置：网站首页>牛客网二叉树题解

牛客网二叉树题解

2022-07-28 11:37:00 【antRain】

牛客网二叉树题解

牛客网面试必刷TOP101

二叉树的前序遍历

int* preorderTraversal(struct TreeNode* root, int* returnSize ) {
    
    int *res = malloc(101*sizeof(int)); 
    *returnSize = 0;
    struct TreeNode** stack = malloc(101*sizeof(struct TreeNode*));
    int top=0;
    struct TreeNode *p=root;
    while (p||top)
    {
    
        // 先把节点压入stack, 访问左孩子
        if(p) {
    
            res[(*returnSize)++] = p->val;
            stack[top++]=p;
            p=p->left;
        } else {
    
            // 左节点为空，访问上一个节点的右孩子
            p = stack[--top];
            p=p->right;
        }
    }
    return res;
}

int* preorderTraversal(struct TreeNode* root, int* returnSize ) {
    
    int *res = malloc(101*sizeof(int)); 
    *returnSize = 0;
    if (!root)return res;
    struct TreeNode** stack = malloc(101*sizeof(struct TreeNode*));
    int top=0;
    struct TreeNode *p=root;
    stack[top++]=p;
    // 栈是后进先出，前序遍历是要先遍历左子树，再遍历右子树
    while (top)
    {
    
        p = stack[--top];
        res[(*returnSize)++] = p->val;
        if(p->right)
           stack[top++]=p->right;
        if (p->left) 
            stack[top++]=p->left;
    }
    return res;
}

// https://zhuanlan.zhihu.com/p/384818393

二叉树的中序遍历

int* inorderTraversal(struct TreeNode* root, int* returnSize ) {
    
    int *res = malloc(1001*sizeof(int)); 
    *returnSize = 0;
    struct TreeNode** stack = malloc(1001*sizeof(struct TreeNode*));
    int top=0;
    struct TreeNode *p=root;
    while (p||top)
    {
    
        // 先把节点压入stack, 访问左孩子
        if(p) {
    
            stack[top++]=p;
            p=p->left;
        } else {
    
            // 左节点为空，访问上一个节点的右孩子
            p = stack[--top];
            res[(*returnSize)++] = p->val;
            p=p->right;
        }
    }
    return res;
}

后序遍历

int* postorderTraversal(struct TreeNode* root, int* returnSize ) {
    
    int *res = malloc(101*sizeof(int)); 
    *returnSize = 0;
    struct TreeNode** stack = malloc(101*sizeof(struct TreeNode*));
    int top=0;
    struct TreeNode *p=root,*r=NULL;
    while (p||top)
    {
    
        // 先把节点压入stack, 访问左孩子
        if(p) {
    
            stack[top++]=p;
            p=p->left;
        } else {
    
            // 左节点为空，访问上一个节点的右孩子
            p = stack[top-1];
            if(p->right&&p->right!=r) p=p->right;
            else {
    
                top--;
                res[(*returnSize)++] = p->val;
                r=p;
                p=NULL;
            }
        }
    }
    return res;
}

求二叉树的层序遍历

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes ) {
    
    // write code here
    int maxlen=1e5+1;
    *returnSize = 0;
    if (!root) return NULL;
    // 初始化列
    *returnColumnSizes = malloc(sizeof(int)*maxlen); 
    
    struct TreeNode** queue = malloc(maxlen*sizeof(struct TreeNode*));
    int f=0,r=0; // 队列的前，后指针
    int** res = malloc(maxlen*sizeof(int *));
    int i=0,j=0; // 表示一维，二维坐标
    res[i] = malloc(sizeof(int)); 

    struct TreeNode*p;
    queue[f++]=root;
    int cur=0,plen=1,len=0,; // 记录，当前遍历层的第几个，当前层的总长度，遍历时对下一层加入队列的个数加+1
    while(r<f) {
    
        p = queue[r++];
        cur ++ ;
        res[i][j++]=p->val;
        if (p->left) {
    
            len ++;
            queue[f++]=p->left;
        }
        if (p->right) {
    
            len ++;
            queue[f++]=p->right;
        }
        if (cur==plen) {
    
            // 上一层节点已遍历完
            (*returnColumnSizes)[i]=j;
            plen = len;
            res[++i] = malloc(plen*sizeof(int));
            len = 0;
            j = 0;
            cur = 0;
        }
    }
    *returnSize = i;
    return res;
}

按之字形顺序打印二叉树

int** Print(struct TreeNode* root, int* returnSize, int** returnColumnSizes ) {
    
    #define MAXN 1501
    *returnSize = 0;
    if (!root) return NULL;
    // 初始化列
    *returnColumnSizes = malloc(sizeof(int)*MAXN); 
    
    struct TreeNode** queue = malloc(MAXN*sizeof(struct TreeNode*));
    int f=0,r=0; // 队列的前，后指针
    int** res = malloc(MAXN*sizeof(int *));
    int i=0,j=0; // 表示一维，二维坐标
    res[i] = malloc(sizeof(int)); 

    struct TreeNode*p;
    queue[f++]=root;
    int cur=0,plen=1,len=0; // 记录，当前遍历层的第几个，当前层的总长度，遍历时对下一层加入队列的个数加+1
    int level = 1; // 表示第几层
    while(r<f) {
    
        p = queue[r++];
        cur ++ ;
        if (level&1)
            res[i][j++]=p->val;
        else 
            res[i][j--]=p->val;
        if (p->left) {
    
            len ++;
            queue[f++]=p->left;
        }
        if (p->right) {
    
            len ++;
            queue[f++]=p->right;
        }
        if (cur==plen) {
    
            // 上一层节点已遍历完
            (*returnColumnSizes)[i]=plen;
            plen = len;
            res[++i] = malloc(plen*sizeof(int));
            len = 0;
            level++;
            j = level&1?0:plen-1;
            cur = 0;
            
        }
    }
    *returnSize = i;
    return res;
}

对称的二叉树

bool judge(struct TreeNode* left,struct TreeNode* right) {
    
    if (!left&&!right) return true;
    if(!left||!right)return false;
    if (left->val != right->val) return false;
    return judge(left->left,right->right) && judge(left->right,right->left);
}


bool isSymmetrical(struct TreeNode* pRoot ) {
    
    // write code here
    if(!pRoot) return true;
    return judge(pRoot->left,pRoot->right);
}

二叉树的最大深度

int max(int a,int b) {
    
    return a>b?a:b;
}

int maxDepth(struct TreeNode* root ) {
    
    if (!root) return 0;
    return 1+max(maxDepth(root->left),maxDepth(root->right));
}

二叉树中和为某一值的路径(一)

bool hasPathSum(struct TreeNode* root, int sum ) {
    
    if (!root) return false;
    if (!root->left&&!root->right) {
    
        return sum==root->val;
    }
    return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);
}

合并二叉树

struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) {
    
    if (!t1) return t2;
    if (!t2) return t1;
    t1->val += t2->val;
    t1->left = mergeTrees(t1->left,t2->left);
    t1->right = mergeTrees(t1->right,t2->right);
    return t1;
}

二叉树的镜像

struct TreeNode* Mirror(struct TreeNode* pRoot ) {
    
    // write code here
    if (!pRoot) return NULL;
    struct TreeNode *p = pRoot->left;
    pRoot->left = pRoot->right;
    pRoot->right = p;
    Mirror(pRoot->left);
    Mirror(pRoot->right);
    return pRoot;
}

重建二叉树

struct TreeNode* makeTree(int *p,int l1,int r1,int *q,int l2,int r2) {
    
    if (l1>r1) return NULL;
    struct TreeNode *tree = malloc(sizeof(struct TreeNode));
    tree->val = p[l2];
    int tmp = l1;
    while(q[tmp]!=p[l2])tmp++;
    int d = tmp-l1;
    tree->left = makeTree(p,l1,tmp-1,q,l2+1,l2+d);
    tree->right  = makeTree(p,tmp+1,r1,q,l2+d+1,r2);
    return tree;
}

struct TreeNode* reConstructBinaryTree(int* pre, int preLen, int* vin, int vinLen ) {
    
    return makeTree(pre,0,preLen-1,vin,0,vinLen-1);
}

输出二叉树的右视图

int* levelOrder(struct TreeNode* root, int* returnSize) {
    
    // write code here
    int maxlen=1e5+1;
    *returnSize = 0;
    if (!root) return NULL;

    struct TreeNode** queue = malloc(maxlen*sizeof(struct TreeNode*));
    int f=0,r=0; // 队列的前，后指针
    int* res = malloc(maxlen*sizeof(int));

    struct TreeNode*p;
    queue[f++]=root;
    int cur=0,len=0,plen=1,i=0;
    while(r<f) {
    
        p = queue[r++];
        cur ++ ;
        if (p->left) {
    
            len ++;
            queue[f++]=p->left;
        }
        if (p->right) {
    
            len ++;
            queue[f++]=p->right;
        }
        if (cur==plen) {
    
            // 上一层节点已遍历完
            res[i++] = p->val;
            plen = len;
            len = 0;
            cur = 0;
        }
    }
    *returnSize = i;
    return res;
}

int* solve(int* xianxu, int xianxuLen, int* zhongxu, int zhongxuLen, int* returnSize ) {
    
    struct TreeNode *tree = makeTree(xianxu,0,xianxuLen-1,zhongxu,0,zhongxuLen-1);
    return levelOrder(tree,returnSize);
}

判断是不是完全二叉树

#define MAXN 105
void travese(struct TreeNode* root,bool *flag,int cur) {
    
    if(!root||cur>MAXN)return;
    flag[cur] = true;
    travese(root->left,flag,2*cur);
    travese(root->right,flag,2*cur+1);
}

bool isCompleteTree(struct TreeNode* root) {
    
    bool flag[MAXN] = {
    false};
    travese(root,flag,1);
    bool res = false;
    for (int i=1;i<MAXN;++i) {
    
        if (res&&flag[i]) return false;
        if (!flag[i]) res = true;
    }
    return true;
}

判断是不是二叉搜索树

#define MAXN 10001
int res[MAXN];
int len=0;

void inorder(struct TreeNode* root){
    
    if (!root) return;
    inorder(root->left);
    res[len++] = root->val;
    inorder(root->right);
}

bool isValidBST(struct TreeNode* root ) {
    
    if (!root) return true;
    inorder(root);
    for(int i=1;i<len;++i) if (res[i]<=res[i-1]) return false;
    return true;
}

判断是不是平衡二叉树

int max(int a,int b) {
    
    return a>b?a:b;
}

int abs(int a){
    
    return a>0?a:-a;
}

int maxDepth(struct TreeNode* root,bool * flag ) {
    
    if (!root || !flag) return 0;
    int l_height = maxDepth(root->left,flag);
    if (!flag) return 0; // 一个优化，用于提前退出
    int r_height = maxDepth(root->right,flag);
    if (!flag) return 0; // 一个优化，用于提前退出
    if (abs(l_height-r_height)>1) *flag = false;
    return 1+max(l_height,r_height);
}

bool IsBalanced_Solution(struct TreeNode* pRoot ) {
    
    // 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
    bool flag = true;
    maxDepth(pRoot,&flag);
    return flag;
}

序列化二叉树

char* Serialize(struct TreeNode* root ) {
    
    if (!root) return NULL;
    #define MAXN 300
    struct TreeNode** queue = (struct TreeNode**) malloc(MAXN*sizeof(struct TreeNode*));
    char* res = (char *) malloc(MAXN*sizeof(char));
    memset(res, 0, MAXN);
    int f=0,r=0; // 队列的前，后指针
    struct TreeNode*p;
    queue[f++]=root;
    int len=0;
    while(r<f) {
    
        p = queue[r++];
        if (!p) {
    
            res[len++]= -1;
            continue;
        } 
        res[len++]=p->val+1;
        queue[f++]=p->left;
        queue[f++]=p->right;
    }
    res[len]=0;
    return res;
}

struct TreeNode* Deserialize(char* str) {
    
    if (!str) return NULL;
    struct TreeNode** queue = (struct TreeNode**) malloc(MAXN*sizeof(struct TreeNode*));
    int f=0,r=0; // 队列的前，后指针
    int len = 0;
    struct TreeNode*p  =  (struct TreeNode*) malloc(sizeof(struct TreeNode));
    p->left=p->right=NULL;
    p->val = str[len++]-1;
    if(p->val<0) p->val+=256; // 在本题题取值范围为0~150， 超过char范围，所以当小于0时需要加256
    struct TreeNode* q;
    queue[f++]=p;
   
    char *s = str;
    while(*s) {
    
        printf("%d ",*(s++)-1);
    }
    printf("\n");
    while (str[len])
    {
    
        p = queue[r++];
        if (str[len]&&str[len++]!=-1) {
    
            q = (struct TreeNode*) malloc(sizeof(struct TreeNode));
            q->val = str[len-1]-1;
            q->left=q->right=NULL;
            if(p->val<0) p->val+=256;
            p->left = q;
            queue[f++]=q;
        }
        if (str[len]&&str[len++]!=-1) {
    
            q = (struct TreeNode*) malloc(sizeof(struct TreeNode));
            q->left=q->right=NULL;
            q->val = str[len-1]-1;
            if(p->val<0) p->val+=256;
            p->right = q;
            queue[f++]=q;
        } 
    }
    return queue[0];
}

二叉树的最近公共祖先

对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大
二叉树的公共祖先分成两种情况

  • p 、q 分别位于最近公共祖先的左右子树
  • p 、q 一个节点就是公共祖先，另一个节点位于它的子树中
// 方法一： 求出根节点到p,q的路径，从根节点开始比，直到第一个节点不同退出
// 方法二：递归查找

int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    
    if(!root) return -1; // 表示没找到
    if (root==p||root==q) return root->val;
    // 在左子树查找是否存在p,q
    int lv = lowestCommonAncestor(root->left,p,q);
    // 在右子树查找是否存在p,q
    int lp = lowestCommonAncestor(root->right,p,q);
    // 左右子树都查找到p和q，表示在不同子树
    if (lv != -1 && lp != -1) {
    
        return root->left; 
    }  
    // p,q在同一个子树，谁先找到表示谁祖先节点
    return lv != -1 ? lv:lp;
}

// 对于二叉搜索而言
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    
    if(!root) return -1;
    struct TreeNode* tmp=root;
    // 设p为最小值，q为最大值
    if (p>q) {
    
        int vmin = p;
        p = q;
        q = vmin;
    }
    // 当p,q位于节点两侧时表示tmp为公共祖先，取等号表示，该节点恰好为p,q
    while (!(p<=tmp->val && q>=tmp->val)) {
    
        if (p>tmp->val) tmp = tmp->right;
        else tmp = tmp->left;
    }
    return tmp->val;
}

二叉搜索树与双向链表

将该二叉搜索树转换成一个排序的双向链表
树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继

// 对于1个节点，需要先求出前驱节点，然后再求出后继节点
static struct TreeNode* p=NULL;
struct TreeNode* Convert(struct TreeNode* pRootOfTree ) {
    
    if (!pRootOfTree) return NULL;
    // 返回中序遍历时的第一个节点，即最左的节点
    struct TreeNode* head = Convert(pRootOfTree->left);
    if (!head) head = pRootOfTree;
    // p 表示遍历该的节点的前驱节点
    pRootOfTree->left = p;
    if (p) p->right = pRootOfTree;
    // 设为下次遍历的前驱节点
    p = pRootOfTree;
    Convert(pRootOfTree->right);
    return head;
}
原网站

版权声明
本文为[antRain]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_41146650/article/details/125919865

边栏推荐

猜你喜欢

随机推荐