【二叉树OJ】常见面试题

Yui_

发布于 2024-10-16 08:29:00

5500

代码可运行

文章被收录于专栏：Yui编程知识Yui编程知识

运行总次数：0

代码可运行

1.单值二叉树

1.2 题目要求

判断所给树的值是否唯一

1.3 深度优先搜索

如何判断单值二叉树树，当且仅当当前节点的左子树和右子树的值都等于当前节点的值。然后根据等值的传递性，所有的树就会相等。为此我们可以运用深度优先遍历的算法，判断当前节点的左右子树的值是否与当前节点相等（注意判断左右子树是否存在），不相等就返回false，相等的话就进行进入二叉树的下一层继续判断，直到最后将结果返回。

bool isUnivalTree(struct TreeNode* root) {
    if(root==NULL)
        return true;
    int cur_val = root->val;
    if(root->left&&root->left->val!=cur_val)//在存在左子树的情况下判断左子树的值是否与当前节点值相等
        return false;
    if(root->right&&root->right->val!=cur_val)//在存在右子树的情况下判断右子树的值是否与当前节点值相等
        return false;
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

2.相同的树

2.1 题目要求

判断两棵树是否相同

2.2 深度优先遍历

现在我们开始考虑经过的每个节点的情况：可以分为3种

p节点和q节点都为NULL，p节点与q节点相同，返回true
p节点和q节点有一个为NULL，p节点与q节点不相同，返回false
p节点和q节点两个都不为NULL，但不相同的情况，返回false
p节点和q节点两个都不为NULL，但相同的情况，继续查找其下一层左右子树了解完这三种情况，写成代码就很简单了。运用深度优先遍历，递归地判断两个二叉树是否相同。

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p==NULL&&q==NULL)
        return true;
    else if(p==NULL||q==NULL)
        return false;
    else if(p->val!=q->val)
        return false;
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

3.对称二叉树

3.1 题目要求

判断二叉树是否为对称二叉树

3.2 深度优先遍历利用相同的树

要判断一个二叉树是否对称还是很简单的，就是判断该节点的左右子树是否"相等"。因为对称的缘故，左右子树的相等应该是镜像相同，那么是不是可以用我们上一题的代码再稍微修改一下呢？这里的镜像相等也是分为4种情况：

p节点和q节点都为NULL，p节点与q节点相同，返回true
p节点和q节点有一个为NULL，p节点与q节点不相同，返回false
p节点和q节点两个都不为NULL，但不相同的情况，返回false
p节点和q节点两个都不为NULL，但相同的情况，继续查找其下一层左右子树唯一不同的就是4的步骤，在传递p的左子树时我们要传递q的右子树，那么传递p的右子树时就需要传递q的左子树了。

bool dfs(struct TreeNode*p,struct TreeNode*q)
{
    if(p==NULL&&q==NULL)
        return true;
    else if(p==NULL||q==NULL)
        return false;
    else if(p->val!=q->val)
        return false;
    return dfs(p->left,q->right)&&dfs(p->right,q->left);
}

bool isSymmetric(struct TreeNode* root) {
    return dfs(root->left,root->right);
}

4.二叉树的前序遍历

4.1 题目要求

按照二叉树的前序遍历将二叉树的值存放到数组中。

4.2 递归方法

这里就将一下，力扣的C语言返回数组的题基本都需要更新returnSize的值，相同会根据这个值判断你返回数组的有效元素个数。在后面用C++后就在需要了

void treepre(int* a,struct TreeNode* root,int*i)
 {
     if(!root)
     {
         return;
     }
     *(a+(*i)++) = root->val;
     treepre(a,root->left,i);
     treepre(a,root->right,i);
     return;

 }
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* a = (int*)malloc(sizeof(int)*100);
    int i = 0;
    treepre(a,root,&i);
    *returnSize = i;
    return a;
}
//C++版
class Solution {
public:
void _dfs(TreeNode* root,vector<int>&res)
{
    if(!root) return;
    res.push_back(root->val);
    _dfs(root->left,res);
    _dfs(root->right,res);
}
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        _dfs(root,res);
        return res;
    }
};

5.二叉树的中序遍历

5.1 题目要求

按照二叉树的中序遍历将二叉树的值存放到数组中

5.2 递归方法

参考前序遍历就好。

 void treepre(int* a,struct TreeNode* root,int*i)
 {
     if(!root)
     {
         return;
     }
     treepre(a,root->left,i);
     *(a+(*i)++) = root->val;
     treepre(a,root->right,i);
     return;

 }
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* a = (int*)malloc(sizeof(int)*100);
    int i = 0;
    treepre(a,root,&i);
    *returnSize = i;
    return a;
}

6.二叉树的后序遍历

6.1 题目要求

按照二叉树的后序遍历将二叉树的值存放到数组中

6.2 递归方法

参考中序遍历题

 void treepre(int* a,struct TreeNode* root,int*i)
 {
     if(!root)
     {
         return;
     }
     treepre(a,root->left,i);
     treepre(a,root->right,i);
     *(a+(*i)++) = root->val;

     return;

 }

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int* a = (int*)malloc(sizeof(int)*100);
    int i = 0;
    treepre(a,root,&i);
    *returnSize = i;
    return a;
}

6.3 迭代方法

我们也可以用迭代的方式实现方法一的递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，具体可以参考下面的代码。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        vector<int> ans;
        while(cur||!st.empty())
        {
            while(cur)//去左树
            {
                st.push(cur);
                cur = cur->left;
            }
            
            TreeNode* tmp = st.top();
            if(tmp->right == nullptr||tmp->right == prev)
            {
                ans.push_back(tmp->val);
                st.pop();
            }
            else
            {
                cur = tmp->right;
            }
            prev = tmp;
            
        }
        return ans;
    }
};

7.另一棵树的子树

7.1 题目要求

判断 root 中是否包含和 subRoot 具有相同结构和节点值的子树

7.2 深度优先搜索

因为题目要我们找root中是否存在一个子树是subRoot，我们直接枚举root的每一个节点然后和subRoot进行相同二叉树的判断。为此写这题只要知道遍历二叉树和相同二叉树的判断就可以了在递归遍历二叉树的过程中如果root的值等于subRoot就可以进入二叉树判断环节了，然后相同二叉树判断的题我们已经写过了，结合一下就是了。

bool isSameTree(struct TreeNode* p,struct TreeNode* q)
{
    if(p==NULL&&q==NULL)
        return true;
    else if(p==NULL||q==NULL)
        return false;
    else if(p->val!=q->val)
        return false;
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL)
        return false;
    if(root->val == subRoot->val)
    {
        if(isSameTree(root,subRoot))
            return true;
    }
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-08-15，如有侵权请联系 cloudcommunity@tencent.com 删除

root