admin管理员组

文章数量:1487745

【二叉树OJ】常见面试题

1.单值二叉树

单值二叉树

1.2 题目要求

判断所给树的值是否唯一

1.3 深度优先搜索

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

代码语言：javascript代码运行次数：0运行复制
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种

  1. p节点和q节点都为NULL，p节点与q节点相同，返回true
  2. p节点和q节点有一个为NULL，p节点与q节点不相同，返回false
  3. p节点和q节点两个都不为NULL，但不相同的情况，返回false
  4. p节点和q节点两个都不为NULL，但相同的情况，继续查找其下一层左右子树 了解完这三种情况，写成代码就很简单了。运用深度优先遍历，递归地判断两个二叉树是否相同。
代码语言：javascript代码运行次数：0运行复制
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种情况：

  1. p节点和q节点都为NULL，p节点与q节点相同，返回true
  2. p节点和q节点有一个为NULL，p节点与q节点不相同，返回false
  3. p节点和q节点两个都不为NULL，但不相同的情况，返回false
  4. p节点和q节点两个都不为NULL，但相同的情况，继续查找其下一层左右子树 唯一不同的就是4的步骤，在传递p的左子树时我们要传递q的右子树，那么传递p的右子树时就需要传递q的左子树了。
代码语言：javascript代码运行次数：0运行复制
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++后就在需要了

代码语言：javascript代码运行次数：0运行复制
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 递归方法

参考前序遍历就好。

代码语言：javascript代码运行次数：0运行复制
 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 递归方法

参考中序遍历题

代码语言：javascript代码运行次数：0运行复制
 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 迭代方法

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

代码语言：javascript代码运行次数：0运行复制
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就可以进入二叉树判断环节了，然后相同二叉树判断的题我们已经写过了，结合一下就是了。

代码语言：javascript代码运行次数：0运行复制
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 删除root遍历递归数组二叉树

本文标签： 二叉树OJ常见面试题

版权声明：本文标题：【二叉树OJ】常见面试题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/shuma/1754815374a3179943.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。