剑指offer之面试题19:二叉树的镜像

题目:

成都创新互联长期为上千余家客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为淄博企业提供专业的网站设计制作、成都网站设计淄博网站改版等技术服务。拥有10年丰富建站经验和众多成功案例,为您定制开发。

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

二叉树的镜像定义:

源二叉树
                   8
                  /  \
                6   10
                / \  / \
              5  7 9 11

镜像二叉树
                  8
                 /  \
              10   6
               / \  / \
            11 9 7  5

思路:还是从根结点开始看,根结点,不用交换,看其左右子树,将其交换,然后在交换后的左右子树上,继续看子树的根结点,看这时的左右子树,进行交换;先交换,后递归

从上图看就是

(1)8为根结点 交换左右结点指向(6,10)--->(10,6)

                    8                    8
                  /  \                  /   \
                6   10    -->     10  6        
                / \  / \               / \  / \             

              5  7 9 11          9 11 5 7   

  (2)10为根结点 交换左右结点的指向 (9,11)--> (11,9)   

                    8                    8
                  /  \                  /   \
                10   6    -->     10  6        
                / \    / \             / \  / \             

              9 11  5 7         11 9 5 7

  (3)6为根结点  交换左右结点的指向  (5,7)--> (7,5)

                    8                    8
                  /  \                  /   \
                10   6    -->     10  6        
                / \    / \             / \  / \             

              11 9  5 7         11 9 7 5

     

/*
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;
        }
        if(pRoot->left!=NULL||pRoot->right!=NULL)
        {
            //先交换
            TreeNode *left=pRoot->right;
            TreeNode *right=pRoot->left;
            pRoot->left=left;
            pRoot->right=right;
        }
        Mirror(pRoot->left);
        Mirror(pRoot->right);
        
    }
};

思路二:利用栈的性质,进行循环访问根结点,交换其左右

代码:

/*
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;
		stack s1;
        s1.push(pRoot);
        while(!s1.empty())
        {
            TreeNode *cur=s1.top();
            s1.pop();
            //先交换
           if(cur->left!=NULL||cur->right!=NULL)
            {
                TreeNode *left=cur->right;
            	TreeNode *right=cur->left;
            	cur->left=left;
            	cur->right=right;
                if(cur->left!=NULL)
                    s1.push(cur->left);
            	if(cur->right!=NULL)
                    s1.push(cur->right);
            }
        }
        
        
    }
};

名称栏目:剑指offer之面试题19:二叉树的镜像
文章转载:http://bzwzjz.com/article/jhohho.html

其他资讯

Copyright © 2007-2020 广东宝晨空调科技有限公司 All Rights Reserved 粤ICP备2022107769号
友情链接: 网站建设 四川成都网站设计 成都网站建设 成都网站建设流程 重庆网站制作 成都网站制作 温江网站设计 上市集团网站建设 成都商城网站建设 外贸营销网站建设 阿坝网站设计 手机网站制作设计 成都网站制作 专业网站设计 手机网站制作 成都网站设计 营销型网站建设 成都网站制作 网站设计制作 成都网站建设 成都网站制作 高端定制网站设计