二叉树的镜像:将一个二叉树的左右子树,调换位置。即下图的形式: 递归的思想是: 从根节点的左右子树进行交换,然后以根节点的左子树为根节点,而后以根节点的右结点为根节
二叉树的镜像:将一个二叉树的左右子树,调换位置。即下图的形式:
递归的思想是:
从根节点的左右子树进行交换,然后以根节点的左子树为根节点,而后以根节点的右结点为根节点,进行左右子树交换。遇到空节点或叶节点直接返回。下面求二叉树镜像的函数代码实现:
template<class T> void MirroTree(TreeNode<T> * root) { if (root == NULL) return; if (root->_left == NULL && root->_right == NULL) return; else { TreeNode<T>* temp = root->_left; root->_left = root->_right; root->_right = temp; } MirroTree(root->_left); MirroTree(root->_right); }
非递归实现思想:
利用stack栈的FILO,即先进后出原则,将根节点先行压入栈中,然后进入栈同时取栈顶结点并pop栈,然后交换左右子树的结点,若根节点的左右子树不为空,即压入栈中,直到栈为空则停止。
下面是非递归实现代码:
template<class T> void MirroTree_NoR(TreeNode<T>* root) { stack<TreeNode<T>*> s; s.push(root); while (s.size()) { TreeNode<T>* Top = s.top(); if (Top->_left != NULL || Top->_right != NULL) { TreeNode<T>* temp = Top->_left; Top->_left = Top->_right; Top->_right = temp; } if (Top->_left != NULL) s.push(Top->_left); if (Top->_right != NULL) s.push(Top->_right); } }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!