欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

tree traversal (树的遍历) - 前序遍历 (preorder traversal) - 二叉树的前序遍历

程序员文章站 2022-07-13 23:17:40
...

tree traversal (树的遍历) - 前序遍历 (preorder traversal) - 二叉树的前序遍历

1. tree traversal (树的遍历)

1.1 深度优先搜索 (depth-first search,DFS)

我们采用深度作为优先级,从根节点开始一直到达某个确定的叶子节点,然后再返回根节点到达另一个分支。深度优先搜索策略可以根据根节点、左孩子树和右孩子树的相对顺序被细分为前序遍历、中序遍历和后序遍历。

前序遍历 (preorder traversal) - 中序遍历 (inorder traversal) - 后序遍历 (postorder traversal)

1.2 广度优先搜索 - 宽度优先搜索 - 横向优先搜索 (breadth-first search,BFS)

我们按照高度顺序一层一层的访问整棵树,高层次的节点将会比低层次的节点先被访问到。

下图中的节点依照不同的策略遍历,访问的顺序均为 1, 2, 3, 4, 5。宽度优先搜索划分层次为 [[1], [2, 3], [4, 5]]
tree traversal (树的遍历) - 前序遍历 (preorder traversal) - 二叉树的前序遍历

2. 二叉树的前序遍历

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

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

输出: [1,2,3]
int* preorderTraversal(struct TreeNode* root, int* returnSize)

输入参数 rootNULL 时,如果 return NULL*returnSize 必须设置为 0

2.1 迭代实现 - 数组模拟栈 (stack) 的操作

从根节点开始,每次迭代弹出当前栈顶元素,并将其孩子节点压入栈中,先压入右孩子再压入左孩子。输出到最终结果的顺序按照 Top -> Bottom 和 Left -> Right,符合前序遍历的顺序。

时间复杂度:访问每个节点恰好一次,时间复杂度为 O(N),其中 N 是节点的个数,即树的大小。
空间复杂度:取决于树的结构,最坏情况存储整棵树,空间复杂度是 O(N)

  1. 设置一个栈,将根节点 push 到栈中。
  2. 循环检测栈是否为空,若不空,则取出栈顶元素,保存其值。
  3. 查看栈顶元素右子节点是否存在,若存在则 push 到栈中。查看栈顶元素左子节点,若存在,则 push 到栈中。
  4. 继续回到 2. 执行,直到栈空。
//============================================================================
// Name        : preorder traversal
// Author      : Yongqiang Cheng
// Version     : Feb 22, 2020
// Copyright   : Copyright (c) 2019 Yongqiang Cheng
// Description : Hello World in C++, Ansi-style
//============================================================================

/*
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/*
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
	int idx = 0, front = 0;
	struct TreeNode* STACK_DATA[256] = { NULL };
	struct TreeNode* pnode = NULL;
	int *ret = (int*) malloc(256 * sizeof(int));

	*returnSize = 0;

	if ((NULL == root) || (NULL == returnSize))
	{
		return NULL;
	}

	front = -1;
	STACK_DATA[++front] = root;

	while (front >= 0)
	{
		pnode = STACK_DATA[front];
		front--;

		ret[idx] = pnode->val;
		idx++;

		if (NULL != pnode->right)
		{
			STACK_DATA[++front] = pnode->right;
		}

		if (NULL != pnode->left)
		{
			STACK_DATA[++front] = pnode->left;
		}
	}

	*returnSize = idx;

	return ret;
}

tree traversal (树的遍历) - 前序遍历 (preorder traversal) - 二叉树的前序遍历

tree traversal (树的遍历) - 前序遍历 (preorder traversal) - 二叉树的前序遍历

tree traversal (树的遍历) - 前序遍历 (preorder traversal) - 二叉树的前序遍历

tree traversal (树的遍历) - 前序遍历 (preorder traversal) - 二叉树的前序遍历

3. 前序遍历 (preorder traversal)

前序遍历 (preorder traversal) 先沿左侧通路自顶而下访问沿途节点,再自底而上依次遍历这些节点的右子树。

tree traversal (树的遍历) - 前序遍历 (preorder traversal) - 二叉树的前序遍历

迭代式前序遍历 (出栈节点以深色示意)
tree traversal (树的遍历) - 前序遍历 (preorder traversal) - 二叉树的前序遍历

References

https://leetcode-cn.com/

相关标签: C - GCC