Solution to the binary tree problem of niuke.com

Niuke interview must brush TOP101

Preorder traversal of two tree

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)
    {
    
        //  First press the node into stack,  Visit left child 
        if(p) {
    
            res[(*returnSize)++] = p->val;
            stack[top++]=p;
            p=p->left;
        } else {
    
            //  Left node is empty , Visit the right child of the previous node 
            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;
    //  The stack is last in, first out , Preorder traversal is to traverse the left subtree first , Traversing right subtree again 
    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

Middle order traversal of binary trees

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)
    {
    
        //  First press the node into stack,  Visit left child 
        if(p) {
    
            stack[top++]=p;
            p=p->left;
        } else {
    
            //  Left node is empty , Visit the right child of the previous node 
            p = stack[--top];
            res[(*returnSize)++] = p->val;
            p=p->right;
        }
    }
    return res;
}

After the sequence traversal

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)
    {
    
        //  First press the node into stack,  Visit left child 
        if(p) {
    
            stack[top++]=p;
            p=p->left;
        } else {
    
            //  Left node is empty , Visit the right child of the previous node 
            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;
}

Find the sequence traversal of binary tree

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes ) {
    
    // write code here
    int maxlen=1e5+1;
    *returnSize = 0;
    if (!root) return NULL;
    //  Initialize Columns 
    *returnColumnSizes = malloc(sizeof(int)*maxlen); 
    
    struct TreeNode** queue = malloc(maxlen*sizeof(struct TreeNode*));
    int f=0,r=0; //  At the front of the line , The back pointer 
    int** res = malloc(maxlen*sizeof(int *));
    int i=0,j=0; //  I mean one dimension , Two dimensional coordinates 
    res[i] = malloc(sizeof(int)); 

    struct TreeNode*p;
    queue[f++]=root;
    int cur=0,plen=1,len=0,; //  Record , The current number of traversal layers , The total length of the current layer , When traversing, add +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) {
    
            //  The upper layer node has been traversed 
            (*returnColumnSizes)[i]=j;
            plen = len;
            res[++i] = malloc(plen*sizeof(int));
            len = 0;
            j = 0;
            cur = 0;
        }
    }
    *returnSize = i;
    return res;
}

Print binary trees in zigzag order

int** Print(struct TreeNode* root, int* returnSize, int** returnColumnSizes ) {
    
    #define MAXN 1501
    *returnSize = 0;
    if (!root) return NULL;
    //  Initialize Columns 
    *returnColumnSizes = malloc(sizeof(int)*MAXN); 
    
    struct TreeNode** queue = malloc(MAXN*sizeof(struct TreeNode*));
    int f=0,r=0; //  At the front of the line , The back pointer 
    int** res = malloc(MAXN*sizeof(int *));
    int i=0,j=0; //  I mean one dimension , Two dimensional coordinates 
    res[i] = malloc(sizeof(int)); 

    struct TreeNode*p;
    queue[f++]=root;
    int cur=0,plen=1,len=0; //  Record , The current number of traversal layers , The total length of the current layer , When traversing, add +1
    int level = 1; //  What level is it 
    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) {
    
            //  The upper layer node has been traversed 
            (*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;
}

Symmetric binary tree

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);
}

The maximum depth of a binary tree

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));
}

The path of a value in a binary tree ( One )

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);
}

Merge binary tree

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;
}

Image of binary tree

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;
}

Reconstruction of binary tree

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);
}

Output the right view of the binary tree

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; //  At the front of the line , The back pointer 
    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) {
    
            //  The upper layer node has been traversed 
            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);
}

Judge whether it is a complete binary tree

#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;
}

Determine whether it is a binary search tree

#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;
}

Judge whether it is a balanced binary tree

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; //  An optimization , For early exit 
    int r_height = maxDepth(root->right,flag);
    if (!flag) return 0; //  An optimization , For early exit 
    if (abs(l_height-r_height)>1) *flag = false;
    return 1+max(l_height,r_height);
}

bool IsBalanced_Solution(struct TreeNode* pRoot ) {
    
    //  It is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1, And both the left and right subtrees are a balanced binary tree .
    bool flag = true;
    maxDepth(pRoot,&flag);
    return flag;
}

Serialize binary tree

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; //  At the front of the line , The back pointer 
    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; //  At the front of the line , The back pointer 
    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; //  In this question, the value range is 0~150,  exceed char Range , So when less than 0 Need to add 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];
}

The nearest common ancestor of a binary tree

For a tree T Two nodes of p、q, Recent public ancestor LCA(T,p,q) Represents a node x, Satisfy x yes p and q Our ancestors and x As deep as possible
The common ancestor of binary tree is divided into two cases

• p 、q Located in the left and right subtrees of the nearest common ancestor
• p 、q A node is a common ancestor , Another node is in its subtree

//  Method 1 ：  Find the root node to p,q The path of , Start from the root node , Until the first node exits differently 
//  Method 2 ： Recursive search 

int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    
    if(!root) return -1; //  I didn't find 
    if (root==p||root==q) return root->val;
    //  Find out whether it exists in the left subtree p,q
    int lv = lowestCommonAncestor(root->left,p,q);
    //  Find out whether it exists in the right subtree p,q
    int lp = lowestCommonAncestor(root->right,p,q);
    //  Both left and right subtrees can be found p and q, Expressed in different subtrees 
    if (lv != -1 && lp != -1) {
    
        return root->left; 
    }  
    // p,q In the same subtree , Who finds the ancestor node first 
    return lv != -1 ? lv:lp;
}

//  For binary search 
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    
    if(!root) return -1;
    struct TreeNode* tmp=root;
    //  set up p Is the minimum ,q Is the maximum 
    if (p>q) {
    
        int vmin = p;
        p = q;
        q = vmin;
    }
    //  When p,q When it is on both sides of the node, it means tmp For the common ancestor , Take the equal sign to indicate , The node happens to be p,q
    while (!(p<=tmp->val && q>=tmp->val)) {
    
        if (p>tmp->val) tmp = tmp->right;
        else tmp = tmp->left;
    }
    return tmp->val;
}

Binary search tree and double linked list

The binary search tree is transformed into a sorted double linked list
The left pointer of the node in the tree needs to point to the precursor , The right pointer of the node in the tree needs to point to the successor

//  about 1 Nodes , You need to find the precursor node first , And then find the subsequent nodes 
static struct TreeNode* p=NULL;
struct TreeNode* Convert(struct TreeNode* pRootOfTree ) {
    
    if (!pRootOfTree) return NULL;
    //  Return the first node when traversing the middle order , That is, the leftmost node 
    struct TreeNode* head = Convert(pRootOfTree->left);
    if (!head) head = pRootOfTree;
    // p  Represents the precursor node of traversing the node 
    pRootOfTree->left = p;
    if (p) p->right = pRootOfTree;
    //  Set as the precursor node of the next traversal 
    p = pRootOfTree;
    Convert(pRootOfTree->right);
    return head;
}