将二叉树变换为源二叉树的镜像如何实现?思路和实现

KLQ 2020-04-29 11:22:38 java常见问答 4120

你知道将一个叉树变换为源二叉树的镜像java要怎样才能实现吗?下面的文章要给大家分享的就是这个方面的内容。

一、题目

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

输入描述:

将二叉树变换为源二叉树的镜像

二、思路和实现

思路1

代码实现:

public class Solution
{
    public void Mirror(TreeNode root)
    {
        reverseTree(root);
    }
    private void reverseTree(TreeNode root)
    {
        //为空则结束
        if (root == null)
        {
            return;
        }
        //假设root两边的子树自己都已经翻转成功了,那么只需要再将左右子树互换一下就成功了
        //交换root的左右子树
        swap(root);
        //左右子树翻转自己去处理就行了,我们规定每个子树的root都跟最终的root处理方式一样即可
        reverseTree(root.left);
        reverseTree(root.right);
    }
    private void swap(TreeNode root)
    {
        TreeNode node = null;
        node = root.left;
        root.left = root.right;
        root.right = node;
    }
}

思路2:

先前序遍历这棵树的每个结点,假如遍历到的结点有子结点,那么就交换它的两个子节点,在交换完所有的非叶子结点的左右子结点之后,就得到了树的镜像。

代码实现:

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null)
            return;
        if(root.left == null && root.right == null)
            return;
         
        TreeNode pTemp = root.left;
        root.left = root.right;
        root.right = pTemp;
         
        if(root.left != null)
            Mirror(root.left);
        if(root.right != null)
            Mirror(root.right);
    }
}

思路3:

非递归

代码实现:

class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        //递归实现
        /*if(pRoot==NULL)
            return;
        TreeNode *ptemp=pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=ptemp;
        if(pRoot->left)
            Mirror(pRoot->left);
        if(pRoot->right)
            Mirror(pRoot->right);*/
        //非递归实现
        if(pRoot==NULL)
            return;
        stack
<TreeNode*> stackNode;
        stackNode.push(pRoot);
        while(stackNode.size()){
            TreeNode* tree=stackNode.top();
            stackNode.pop();
            if(tree->left!=NULL || tree->right!=NULL){
                TreeNode *ptemp=tree->left;
                tree->left=tree->right;
                tree->right=ptemp;
            }
            if(tree->left)
                stackNode.push(tree->left);
            if(tree->right)
                stackNode.push(tree->right);
        }
    }
};

以上的思路和实现方式你都了解了吗?以上内容仅供参考哦。

更多java实例,请继续关注奇Q工具网的java实例专栏了解吧!