我是靠谱客的博主 忧心小天鹅,最近开发中收集的这篇文章主要介绍【LeetCode】—— 二叉树的遍历,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

一、二叉树的前序遍历(根节点,左子树,右子树)

1.1 题目描述

给定一个二叉树,返回它的 前序 遍历。

示例:

输入: [1,null,2,3]  
   1
    
     2
    /
   3 

输出: [1,2,3]
1.2 代码实现
int treeSize(struct TreeNode* root)//计算所遍历二叉树节点的个数
{
    if(root == NULL)
        return 0;
    else
        return treeSize(root->left)+treeSize(root->right)+1;
}
//为方便递归构造的子函数
void _preorderTraversal(struct TreeNode* root,int* preorder,int* pindex)
{
    if(root == NULL)
        return;
    
    preorder[*pindex] = root->val;//访问根节点
    ++(*pindex);
    
    _preorderTraversal(root->left,preorder,pindex);//访问左子树
    _preorderTraversal(root->right,preorder,pindex);//访问右子树
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = treeSize(root);
    int* preorder = (int*)malloc(*returnSize * sizeof(int));
    
    int index = 0;
    _preorderTraversal(root,preorder,&index);
    
    return preorder;
}

二、二叉树的中序遍历(左子树,根节点,右子树)

2.1 题目描述

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    
     2
    /
   3

输出: [1,3,2]
2.2 代码实现
int treeSize(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    else
        return treeSize(root->left)+treeSize(root->right)+1;
}
void _postorderTraversal(struct TreeNode* root,int* postorder,int* pindex)
{
    if(root == NULL)
        return;
    
     _postorderTraversal(root->left,postorder,pindex);
      postorder[*pindex] = root->val;
      ++(*pindex);
     _postorderTraversal(root->right,postorder,pindex);
    
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = treeSize(root);
    int* postorder = (int*)malloc(*returnSize*sizeof(int));
    
    int index = 0;
    _postorderTraversal(root,postorder,&index);
    
    return postorder;
}

三、二叉树的后序遍历(左子树,右子树,根节点)

3.1 题目描述

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    
     2
    /
   3

输出: [3,2,1]
3.2 代码实现
int treeSize(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    else
        return treeSize(root->left)+treeSize(root->right)+1;
}
void _postorderTraversal(struct TreeNode* root,int* postorder,int* pindex)
{
    if(root == NULL)
        return;
    
    _postorderTraversal(root->left,postorder,pindex);
     _postorderTraversal(root->right,postorder,pindex);
    postorder[*pindex] = root->val;
    ++(*pindex);
    
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = treeSize(root);
    int* postorder = (int*)malloc(*returnSize*sizeof(int));
    
    int index = 0;
    _postorderTraversal(root,postorder,&index);
    
    return postorder;
}

最后

以上就是忧心小天鹅为你收集整理的【LeetCode】—— 二叉树的遍历的全部内容,希望文章能够帮你解决【LeetCode】—— 二叉树的遍历所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(52)

评论列表共有 0 条评论

立即
投稿
返回
顶部