剑指offer（18）——C++实现二叉树镜像

川长思鸟来 2024-04-17 05:36 90阅读 0赞

# 题目 #

操作给定的二叉树，将其变换为源二叉树的镜像

# 考察点 #

*  二叉树
 *  二叉树遍历

# 解题思路 #

分析本质就是左右节点的交换。先前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子节点，当交换完所有的非叶子结点的左右子结点之后，就得到了树的镜像。

# 完整代码 #

/*18-二叉树的镜像*/
    #include<iostream>
    #include<stack>
    using namespace std;
    
    struct TreeNode {
        
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
        
    	}
    };
    class Solution {
        
    public:
    	void Mirror(TreeNode *pRoot) {
        
    		if (pRoot == NULL) return;
    		
    		TreeNode *temp;
    		temp = pRoot->left;
    		pRoot->left = pRoot->right;
    		pRoot->right = temp;
    
    		if (pRoot->left)
    			Mirror(pRoot->left);
    		if (pRoot->right)
    			Mirror(pRoot->right);
    	}
    };
    int main()
    {
        
    	TreeNode* A1 = new TreeNode(1); TreeNode* A2 = new TreeNode(2); TreeNode* A3 = new TreeNode(3);
    	TreeNode* A4 = new TreeNode(4); TreeNode* A5 = new TreeNode(5); TreeNode* A6 = new TreeNode(6); TreeNode* A7 = new TreeNode(7);
    	A1->left = A2; A1->right = A3; A2->left = A4; A2->right = A5; A3->left = A6; A3->right = A7;
    	//打印原二叉树，前序遍历
    	stack<TreeNode*> stack;
    	stack.push(A1);
    	while (!stack.empty())
    	{
        
    		A1 = stack.top();
    		cout << A1->val << "";
    		stack.pop();
    		if (A1->right != NULL)
    			stack.push(A1->right);
    		if (A1->left != NULL)
    			stack.push(A1->left);
    	}
    	cout << endl;
    	Solution s;
    	s.Mirror(A1);
    	return 0;
    }