(leetcode)二叉树的前序遍历-c语言实现（二叉树的先序遍历c语言）

25-02-18 15

这篇文章主要围绕(leetcode)二叉树的前序遍历-c语言实现和二叉树的先序遍历c语言展开，旨在为您提供一份详细的参考资料。我们将全面介绍(leetcode)二叉树的前序遍历-c语言实现的优缺点，解

这篇文章主要围绕(leetcode)二叉树的前序遍历-c语言实现和二叉树的先序遍历c语言展开，旨在为您提供一份详细的参考资料。我们将全面介绍(leetcode)二叉树的前序遍历-c语言实现的优缺点，解答二叉树的先序遍历c语言的相关问题，同时也会为您带来(leetcode)二叉树的层次遍历-c语言实现、leecode刷题（28）-- 二叉树的前序遍历、LeetCode 102二叉树的层序遍历&103二叉树锯齿形遍历&104二叉树的最大深度、LeetCode 144 ——二叉树的前序遍历的实用方法。

本文目录一览：

(leetcode)二叉树的前序遍历-c语言实现（二叉树的先序遍历c语言）
(leetcode)二叉树的层次遍历-c语言实现
leecode刷题（28）-- 二叉树的前序遍历
LeetCode 102二叉树的层序遍历&103二叉树锯齿形遍历&104二叉树的最大深度
LeetCode 144 ——二叉树的前序遍历

(leetcode)二叉树的前序遍历-c语言实现（二叉树的先序遍历c语言）

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

示例:

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

输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

用c语言来实现比较麻烦，现在大概介绍下我的思路，首先题目先要实现一个前序遍历，如果用递归，会比较简单，几行代码就可以实现，但是现在要求使用迭代发来实现。整个遍历过程是，访问根节点，然后遍历其左子树，然后再看左子树是否有其左孩子和右孩子。因为在查看左孩子之后，还要再查看根节点的右孩子，所以每次需要把根节点记录下来，需要存在栈中。所以我们需要实现一个栈，有压栈和出栈操作。另外我们需要一个链表来存放已经访问过的节点，到最后，需要把这些节点统一存储到一个数组中，然后返回。

下面来看下我码的代码

/* 链表节点 用于存储输出结果 */
struct listNode {
    int val;
    struct listNode *next;
};

struct list {
    int count;
    struct listNode *head;
    struct listNode *tail;
};

/* 栈节点，用于存储已经遍历过的根节点 */
struct StackNode
{
    void *entry;
    struct StackNode *next;
};

struct stack {
    struct StackNode *top;
};

void init_stack(struct stack *s)
{
    s->top = NULL;
}

void stack_push(struct stack *s, void *np)
{
    struct StackNode *node = malloc(sizeof(struct StackNode));
    node->entry = np;
    node->next = s->top;
    s->top = node;
};

void *stack_pop(struct stack *s)
{
    struct StackNode *np = s->top;
    void *node = np->entry;
    s->top = np->next;
    free(np);
    return node;
};

bool isEmpty(struct stack *s)
{
    return (s->top == NULL) ? true : false;
}

void init_list(struct list *l)
{
    l->count = 0;
    l->head = NULL;
    l->tail = NULL;
}

void add_new_node(struct list *l, struct listNode *node)
{
    if (!l->head)
    {
        l->head = node;
        l->tail = node;
        l->count = 1;
        return;
    }
    
    l->tail->next = node;
    l->tail = node;
    l->count++;
}

这些是辅助函数

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    struct TreeNode *pNode = root;
    struct listNode *newNode = NULL;
    struct list *l = malloc(sizeof(struct list));
    struct stack *s = malloc(sizeof(struct stack));
    int *r = NULL;
    int i = 0;
    struct listNode *head = NULL;
    init_list(l);
    init_stack(s);
    
    while (pNode != NULL || !isEmpty(s))
    {
        if (pNode != NULL)
        {
            newNode = malloc(sizeof(struct listNode));
            newNode->val = pNode->val;
            newNode->next = NULL;
            add_new_node(l, newNode);
            stack_push(s, (void *)pNode);
            pNode = pNode->left;
        }
        else
        {
            pNode = (struct TreeNode *)stack_pop(s);
            pNode = pNode->right;            
        }        
    }
    
    r = malloc(sizeof(int) * l->count);
    head = l->head;
    while(head && i < l->count)
    {
        r[i] = head->val;
        i++;
        head = head->next;
    }
    *returnSize = l->count;
    
    return r;    
}

这个是具体的前序遍历函数。

对应的中序遍历的核心代码如下：

while (pNode != NULL || !isEmpty(s))
    {
        if (pNode != NULL)
        {
            stack_push(s, (void *)pNode);
            pNode = pNode->left;
        }
        else { pNode = (struct TreeNode *)stack_pop(s); newNode = malloc(sizeof(struct listNode)); newNode->val = pNode->val; newNode->next = NULL; add_new_node(l, newNode); pNode = pNode->right; } }

后序遍历如下：

while (pNode != NULL || !isEmpty(s))
    {
        if (pNode != NULL)
        {
            stack_push(s, (void *)pNode);
            pNode = pNode->left;
        }
        else { seek = (struct TreeNode *)stack_seek(s); if (seek->right == NULL || last == seek->right) { stack_pop(s); newNode = malloc(sizeof(struct listNode)); newNode->val = seek->val; newNode->next = NULL; add_new_node(l, newNode); last = seek; } else { pNode = seek->right; } } }

(leetcode)二叉树的层次遍历-c语言实现

这段代码，在后面跑测试用例时，出现了stack-overflow，但是原因还不清楚。

问题如下：

二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

因为要输出一个二维数组，那么我需要定义一个两重链表，具体定义如下：

/* 链表节点 用于存储输出结果 */
struct listNode {
    int val;
    struct listNode *next;
};

struct list {
    int count;
    struct listNode *head;
    struct listNode *tail;
    struct list *next;
};

struct list_list
{
    int count;
    struct list *head;
    struct list *tail;
};

链表的一些操作如下：

void init_list(struct list *l)
{
    l->count = 0;
    l->head = NULL;
    l->tail = NULL;
    l->next = NULL;
}

void init_list_list(struct list_list *l)
{
    l->count = 0;
    l->head = NULL;
    l->tail = NULL;
}

void add_new_node(struct list *l, struct listNode *node)
{
    if (!l->head)
    {
        l->head = node;
        l->tail = node;
        l->count = 1;
        return;
    }
    
    l->tail->next = node;
    l->tail = node;
    l->count++;
}

void add_new_list(struct list_list *ll, struct list *l)
{
    if (ll->head == NULL)
    {
        ll->head = l;
        ll->tail = l;
        ll->count = 1;
        return;
    }
    
    ll->tail->next = l;
    ll->tail = l;
    ll->count++;
}

链表创建如下：

struct list_list * create_list_list()
{
    struct list_list *ll = malloc(sizeof(struct list_list));
    if (ll)
    {
        init_list_list(ll);
    }
    return ll;
}
struct list * create_list()
{
    struct list *l = malloc(sizeof(struct list));
    if (l)
    {
        init_list(l);
    }
    
    return l;
}

另外需要定义一个队列，用于存放每个树节点

/* 队列节点，用于存储已经遍历过的根节点 */
struct queue_node
{
    void *entry;
    struct queue_node *next;
};

struct queue {
    struct queue_node *front;
    struct queue_node *rear;
};

队列的一些简单操作实现如下：

/* 队列节点，用于存储已经遍历过的根节点 */
struct queue_node
{
    void *entry;
    struct queue_node *next;
};

struct queue {
    struct queue_node *front;
    struct queue_node *rear;
};

void init_queue(struct queue *q)
{
    q->front = NULL;
    q->rear = NULL;
}

void queue_push(struct queue *q, void *np)
{
    struct queue_node *node = malloc(sizeof(struct queue_node));
    node->entry = np;
    node->next = NULL;
    
    if (q->rear == NULL)
    {
        q->rear = node;
        q->front = node;
    }
    else
    {
        q->rear->next = node;
        q->rear = node;
    }  
}

void *queue_pop(struct queue *q)
{
    struct queue_node *np = q->front;
    void *entry = NULL;
    if (np)
    {
        entry = np->entry;
        if (np->next == NULL)
            q->rear = NULL;
        q->front = np->next;
        free(np);        
    }
    
    return entry;
}

struct queue * create_queue()
{
    struct queue *q = malloc(sizeof(struct queue));
    if (q)
    {
        init_queue(q);
    }
    return q;
}

主函数的具体实现思想为，遍历根节点，将其存入队列中，然后在队列中插入一个flag标记，之后进入一个while循环，循环中，每次从队列中取出一个成员，将该成员存入到用于输出的二层链表中，然后判断其左右孩子是否为空，不为空，则其左右孩子入队列。然后再循环，当从队列中取出的是flag标志后，并且队列中还没空，那么就在这个队列中再插入一个flag标志，表示这一层的遍历结束，可以输出这一层的链表。如此循环，直到所有节点都入队列，读到最后一个flag标记，并且队列为空，那么整个遍历流程结束。后面就是把二层链表输出成一个二维数组。

代码如下：

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    struct list_list *ll;
    struct list *subList;
    struct listNode *head;    
    struct queue *q;
    struct TreeNode *pNode = NULL;
    struct listNode *newnode = NULL;
    int **r;
    int *subr;
    struct list *l;
    int i,j;
    int *size;
    int *resize;
    
    if (!root || !returnSize || !returnColumnSizes)
        return;
    
    q = create_queue();
    ll = create_list_list();
    l = create_list();
    add_new_list(ll, l);
    queue_push(q, (void*)root);
    queue_push(q, FINISH_FALG);

    while (q->front != NULL)
    {
        pNode = (struct TreeNode *)queue_pop(q);
        if (pNode == FINISH_FALG)
        {
            if (q->front == NULL)
                break;
            /* 创建新的链表，在总链表中插入新的链表 */
            l = create_list();
            add_new_list(ll, l);
            
            /* 在当前队列中再插入一个终结标志 */
            queue_push(q, FINISH_FALG);
            continue;
        }
        
        /* 该节点插入到当前链表中 */
        newnode = create_node(pNode->val);
        add_new_node(l, newnode);
        
        /* 将当前节点的左右孩子加入队列中 */
        if (pNode->left != NULL)
        {
            queue_push(q, (void*)pNode->left);
        }
        if (pNode->right != NULL)
        {
            queue_push(q, (void*)pNode->right);
        }        
    }
    
    r = (int **)malloc(sizeof(int *) * ll->count);
    resize = (int *)malloc(sizeof(int *) * ll->count);
    subList = ll->head;
    while(subList && i < ll->count)
    {
        subr = (int *)malloc(sizeof(int) * subList->count);
        head = subList->head;
        j = 0;
        while(head && j < subList->count)
        {
            subr[j] = head->val;
            j++;
            head = head->next;
        }

        resize[i] = subList->count;
        
        r[i] = subr;
        i++;
        subList = subList->next;
    }
    *returnSize = ll->count;
    *returnColumnSizes = resize;
    return r;
}

leecode刷题（28）-- 二叉树的前序遍历

二叉树的前序遍历

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

示例:

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

输出: [1,2,3]

思路

这道题我们用递归的思想很容易就能解出来。前序遍历，我们先处理根，之后是左子树，然后是右子树。

代码如下

Java 描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root != null) {
            list.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return list;
    }
}

python 描述

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        if root is not None:
            res = res + [root.val]
            res = res + self.preorderTraversal(root.left)
            res = res + self.preorderTraversal(root.right)
        return res

总结

两门语言的代码量差不多，用递归几行就能搞定，对比如下：

对比.png

LeetCode 102二叉树的层序遍历&103二叉树锯齿形遍历&104二叉树的最大深度

微信搜一搜：bigsai
大家都在关注的刷题、学习数据结构和算法宝藏项目
关注回复进群即可加入力扣打卡群，欢迎划水。近期打卡：
LeetCode 97交错字符串(动态规划)
LeetCode 98验证二叉搜素树(中序遍历)&99恢复二叉搜索树
LeetCode 100相同的树&101对称二叉树

二叉树的层序遍历

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

分析
二叉树层序遍历过程详细看这篇，直接套魔板即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   
   
   
    public List<List<Integer>> levelOrder(TreeNode root) {
   
   
   
       List<List<Integer>>list=new ArrayList<List<Integer>>();
        if(root==null)return list;
		 Queue<TreeNode>q1=new ArrayDeque<TreeNode>();
		 q1.add(root);
		 while (!q1.isEmpty()) {
   
   
   
			int size=q1.size();
			List<Integer>value=new ArrayList<Integer>();
			for(int i=0;i<size;i++)
			{
   
   
   
				TreeNode pNode=q1.poll();
				if(pNode.left!=null)
					q1.add(pNode.left);
				if(pNode.right!=null)
					q1.add(pNode.right);
				value.add(pNode.val);
			}
			list.add(value);
		}
		 return list;
    }
}

二叉树锯齿形遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

给定二叉树 [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层序遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

分析：
就是一个特殊的层序遍历。更换层的时候需要更换节点顺序，这需要我们用两个内存空间配合达到分清奇偶的目的。这里有的是从左到右，有的是从右到左，理论上可以借助栈将集合的元素反转但是没必要。我用两个List集合直接刚就行了。
首先进行分析：

第一行从左到右，第二行从右到左，第三行从左到右。两个list装的是节点，而还需要每次遍历根据奇数和偶数的特性将节点装起来。
(普遍方法)你可以全部按照正常的顺序分层装起来，只不过如果偶数层遍历的时候从右往左加进结果集合。比较好想，容易操作，但是偶数层在添加节点时候不能同时遍历。
但是笔者瞎搞发现一个规律。全部从右往左遍历。只不过在奇数行先添加(左后右)。而偶数行进行右左添加，相当于这个顺序操作一次被颠倒一次，每次添加节点都可以直接访问而不需要单独的访问。(这个方法可能复杂了上面一条其实就可以了)

实现代码为：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   
   
   
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
   
   
   
        List<List<Integer>>list=new ArrayList<List<Integer>>();
			if(root==null)return list;
			 ArrayList<TreeNode>nodelist1=new ArrayList<TreeNode>();//用来模拟堆栈用
			 ArrayList<TreeNode>nodelist2=new ArrayList<TreeNode>();
			 nodelist1.add(root);
			 int num=1;//做奇数偶数
			 while (!nodelist1.isEmpty()||!nodelist2.isEmpty()) {
   
   
   
				 ArrayList<Integer>team=new ArrayList<Integer>();
				if(num%2==1) {
   
   
   
					for(int i=nodelist1.size()-1;i>=0;i--)
					{
   
   
   
						
						TreeNode teamNode=nodelist1.get(i);
						team.add(teamNode.val);
						if(teamNode.left!=null)nodelist2.add(teamNode.left);
						if(teamNode.right!=null)nodelist2.add(teamNode.right);
					}
					nodelist1.clear();
				}
				else {
   
   
   
					for(int i=nodelist2.size()-1;i>=0;i--)
					{
   
   
   
						
						TreeNode teamNode=nodelist2.get(i);
						team.add(teamNode.val);
						if(teamNode.right!=null)nodelist1.add(teamNode.right);
						if(teamNode.left!=null)nodelist1.add(teamNode.left);
						
					}
					nodelist2.clear();
				}
				list.add(team);
				num++;
			}
			return list;
    }
}

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

分析
可以使用二叉树的遍历同时记录深度，保存最大的深度即可。
具体代码为：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
   
   
   
   int maxhigh;
	 public int maxDepth(TreeNode root) {
   
   
   
		 maxDepth(root,0);
		 return maxhigh;
	 }
	private void maxDepth(TreeNode root, int high) {
   
   
   
		// TODO Auto-generated method stub
		if(high>maxhigh)
			maxhigh=high;
		if(root==null)
			return ;
		else {
   
   
   
			maxDepth(root.left, high+1);
			maxDepth(root.right, high+1);
		}
	}
}

原创不易，bigsai请你帮两件事帮忙一下:

star支持一下，您的肯定是我在平台创作的源源动力。
微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

本文同步分享在博客“Big sai”（CSDN）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

LeetCode 144 ——二叉树的前序遍历

1. 题目

2. 解答

2.1. 递归法

定义一个存放树中数据的向量 data，从根节点开始，如果节点不为空，那么

1. 将当前节点的数值加入到 data 中
1. 递归得到其左子树的数据向量 temp，将 temp 合并到 data 中去
1. 递归得到其右子树的数据向量 temp，将 temp 合并到 data 中去

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        
        vector<int> data = {};
        vector<int> temp = {};

        if (root != NULL)
        {
            data.push_back(root->val);
            temp = preorderTraversal(root->left);
            data.insert(data.end(),temp.begin(),temp.end());
            temp = preorderTraversal(root->right);
            data.insert(data.end(),temp.begin(),temp.end());
        }
        
        return data;         
    }
};

2.2. 迭代法

定义一个存放树中节点的栈 node_stack 和存放数据的向量 data，从根节点开始，如果节点不为空或者栈非空，循环以下过程：

1. 如果节点非空，将节点的值加入 data，如果节点有右孩子，将节点右孩子压入栈，节点指向其左孩子，循环直到节点为空
1. 如果节点为空，栈非空，则弹出栈顶节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {

        vector<int> data = {};
        stack<TreeNode*> node_stack;
        TreeNode* temp = root;
        
        while (temp || !node_stack.empty())
        {
            while(temp != NULL)
            {
                data.push_back(temp->val);
                if (temp->right)    node_stack.push(temp->right);
                temp = temp->left;
            }
            
            // 若最后一个节点没有右子节点，栈为空
            if (!node_stack.empty()) // 栈非空
            {
                temp = node_stack.top();
                node_stack.pop();
            }
        }
        
        return data; 
    }
};

2.3. Morris 遍历法

前面两种方法要么需要函数栈要么需要人工栈，其空间复杂度为 $O(n)$，而 Morris 遍历法可以做到在不影响时间复杂度的情况下做到空间复杂度为 $O(1)$。

定义一个存放数据的向量 data，从根节点开始，如果当前节点非空，循环以下过程：

1. 如果当前节点没有左孩子，将当前节点的值加入到 data 中，当前节点指向其右孩子
1. 如果当前节点有左孩子，则寻找当前节点的前驱节点，即节点值小于该节点值并且值最大的节点，也即当前节点左子树中值最大的节点
- a) 如果前驱节点没有右孩子，前驱节点右孩子指向当前节点，将当前节点的值加入到 data 中，当前节点指向其左孩子
- b) 如果前驱节点右孩子为当前节点，当前节点指向其右孩子，前驱节点右孩子设为空（恢复原有树结构）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {

        vector<int> data = {};
        TreeNode* cur = root;
        TreeNode* pre = NULL;

        while (cur)
        {
            if (cur->left == NULL)
            {
                data.push_back(cur->val);
                cur = cur->right;
            }
            
            else
            {

                // 寻找前驱结点
                pre = cur->left;
                while (pre->right != cur && pre->right)
                {
                    pre = pre->right;
                }
                
                if (pre->right == NULL)
                {
                    data.push_back(cur->val);
                    pre->right = cur;
                    cur = cur->left;
                }
                else
                {
                    cur = cur->right;
                    pre->right = NULL;
                }
            }
        }
        
        return data;
        
    }
};

参考资料

获取更多精彩，请关注「seniusen」!

今天的关于(leetcode)二叉树的前序遍历-c语言实现和二叉树的先序遍历c语言的分享已经结束，谢谢您的关注，如果想了解更多关于(leetcode)二叉树的层次遍历-c语言实现、leecode刷题（28）-- 二叉树的前序遍历、LeetCode 102二叉树的层序遍历&103二叉树锯齿形遍历&104二叉树的最大深度、LeetCode 144 ——二叉树的前序遍历的相关知识，请在本站进行查询。

本文标签：