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

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

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

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

symmetric [sɪ'metrɪk]:adj. 对称的,匀称的

1. 二叉搜索树 (binary search tree) - 对称二叉树

  1. 如果所给的根节点为空,那么它是对称二叉树。
  2. 如果所给的根节点不为空,当它的左子树与右子树对称时,那么它是对称二叉树。
  3. 如果左子树的左孩子与右子树的右孩子对称,左子树的右孩子与右子树的左孩子对称,那么左子树和右子树对称。
  4. 分析可以递归的点 (递归点):判断左子树与右子树对称的条件时,其跟两树的孩子的对称情况有关系。函数 function_B (左树, 右树) 功能是返回是否对称。
    函数 function_B (左树, 右树):左树节点值等于右树节点值且 函数function_B (左树的左子树, 右树的右子树)函数 function_B (左树的右子树, 右树的左子树) 均为真才返回真。

1.1 递归

如果一个树的左子树与右子树镜像对称,那么这个树是对称的。

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

如果同时满足下面的条件,两个树互为镜像:

  1. 它们的两个根结点具有相同的值。
  2. 左树的左节点 == 右树的右节点
  3. 左树的右节点 == 右树的左节点

就像人站在镜子前审视自己那样,镜中的反射与现实中的人具有相同的头部,但反射的右臂对应于人的左臂,反之亦然。

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

  • 时间复杂度:O(n)。遍历整个输入树一次,总的运行时间为 O(n),其中 n 是树中结点的总数。
  • 空间复杂度:递归调用的次数受树的高度限制。在最糟糕情况下,树是线性的,其高度为 O(n)。在最糟糕的情况下,由栈上的递归调用造成的空间复杂度为 O(n)

1.2 迭代

除了递归的方法外,也可以利用两个栈 (stack) 进行迭代。两个栈 (stack) 初始化为 root->leftroot->right。每次提取两个结点并比较它们的值。然后,将两个结点的左右子结点按相反的顺序插入栈 (stack) 中。当队列为空或者检测到树不对称 (即从队列中取出两个不相等的连续结点) 时,该算法结束。

要判断二叉树是不是对称,只需要访问镜像元素值是否相等,即对左右子树做相反顺序的遍历即可。

根节点的左子树进行前序遍历 [DLR,首先访问根结点,然后前序遍历其左子树,最后前序遍历其右子树],同时对根节点的右子树进行 [DRL,首先访问根结点,然后前序遍历其右子树,最后前序遍历其左子树] 遍历。

首先查看左右子树的当前节点,然后对于左子树采用 DLR 方式遍历的同时,对于右子树采用 DRL 方式遍历,这样同时访问的两个结点是镜像位置的两个结点,若结点值不同,则不对称。

2. 对称二叉树

给定一个二叉树,检查它是否是镜像对称的。

例如二叉树 [1, 2, 2, 3, 4, 4, 3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1, 2, 2, null, 3, null, 3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

递归和迭代两种方法解决问题。

//============================================================================
// Name        : preorder traversal
// Author      : Yongqiang Cheng
// Version     : Feb 22, 2020
// Copyright   : Copyright (c) 2020 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;
 * };
 */

bool isSymmetric(struct TreeNode* root)
{
	int front_l = 0, front_r = 0;
	struct TreeNode* STACK_L[512] = { NULL };
	struct TreeNode* STACK_R[512] = { NULL };
	struct TreeNode* pnode = NULL;
	struct TreeNode* qnode = NULL;

	if (NULL == root)
	{
		return true;
	}

	front_l = -1;
	front_r = -1;

	STACK_L[++front_l] = root->left;
	STACK_R[++front_r] = root->right;

	while (front_l >= 0)
	{
		pnode = STACK_L[front_l];
		qnode = STACK_R[front_r];
		front_l--;
		front_r--;

		if ((NULL == pnode) && (NULL == qnode))
		{
			continue;
		}

		if ((NULL == pnode) || (NULL == qnode))
		{
			return false;
		}

		if (pnode->val != qnode->val)
		{
			return false;
		}

		++front_l;
		STACK_L[front_l] = pnode->right;
		++front_l;
		STACK_L[front_l] = pnode->left;

		++front_r;
		STACK_R[front_r] = qnode->left;
		++front_r;
		STACK_R[front_r] = qnode->right;
	}

	return true;
}

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

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

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

//============================================================================
// Name        : preorder traversal
// Author      : Yongqiang Cheng
// Version     : Feb 22, 2020
// Copyright   : Copyright (c) 2020 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;
 * };
 */

bool isSymmetric(struct TreeNode* root)
{
	int front_l = 0, front_r = 0;
	struct TreeNode* STACK_L[512] = { NULL };
	struct TreeNode* STACK_R[512] = { NULL };
	struct TreeNode* pnode = NULL;
	struct TreeNode* qnode = NULL;

	if (NULL == root)
	{
		return true;
	}

	front_l = -1;
	front_r = -1;

	STACK_L[++front_l] = root->left;
	STACK_R[++front_r] = root->right;

	while (front_l >= 0)
	{
		pnode = STACK_L[front_l];
		qnode = STACK_R[front_r];
		front_l--;
		front_r--;

		if ((NULL == pnode) && (NULL == qnode))
		{
			continue;
		}

		if ((NULL == pnode) || (NULL == qnode))
		{
			return false;
		}

		if (pnode->val != qnode->val)
		{
			return false;
		}

		STACK_L[++front_l] = pnode->right;
		STACK_L[++front_l] = pnode->left;

		STACK_R[++front_r] = qnode->left;
		STACK_R[++front_r] = qnode->right;
	}

	return true;
}

References

https://leetcode-cn.com/

相关标签: C - GCC