镜像二叉树

Question

我正在尝试查找二叉树的镜像。以下是我目前所做的：

import treetoolbox.*;
public class MirrorTree extends BinaryTree<String> {
    public MirrorTree(String key) {
        this(null, key, null);
    }
    public MirrorTree(MirrorTree left, String key, MirrorTree right) {
        this.key = key;
        this.left = left;
        this.right = right;
        root = this;
    }
    public MirrorTree mirrorSymmetricTree() {
        if (root == null) {
            return null;
        }
        final MirrorTree left = (MirrorTree) root.left;
        right = root.right;
        root.left = mirrorSymmetricTree(right);
        root.right = mirrorSymmetricTree(left);
        return (MirrorTree) root;
    }
    public static MirrorTree mirrorSymmetricTree(BinaryTree<String> t) {
        return null;
    }
}

我做错了什么？问题应该在这一部分：

if (root == null) {
    return null;
}
final MirrorTree left = (MirrorTree) root.left;
right = root.right;
root.left = mirrorSymmetricTree(right);
root.right = mirrorSymmetricTree(left);
return (MirrorTree) root;

但我想我错过了什么。

Answer 1

删除此函数：

public static MirrorTree mirrorSymmetricTree(BinaryTree<String> t) {
    return null;
}

将参数添加到此函数以使其递归：

public MirrorTree mirrorSymmetricTree(BinaryTree<String> t) {
    if (root == null) {
        return null;
    }
    final MirrorTree left = (MirrorTree) root.left;
    right = root.right;
    root.left = mirrorSymmetricTree(right);
    root.right = mirrorSymmetricTree(left);
    return (MirrorTree) root;
}

Answer 2

您的问题在这里：

public static MirrorTree mirrorSymmetricTree(BinaryTree<String> t) {
    return null;
}

你用这种方法什么都没做！

Answer 3

假设您使用的是类似于本文档的BinaryTree<E>

你可以看到我的解决方案的实时版本

这就是BinaryTree<E>的构建方式，其中BinaryTree<E>是二进制树节点本身，树中的每个节点本身就是一棵树。这就是BinaryTree<E>的插入方法看起来像的原因

public void insert(T value)
{
    if (this.value == null)
    {
        this.value = value;
        return;
    }
    else
    {
        if (this.value.compareTo(value) >= 0)
        {
            if (this.left == null)
                this.left = new BinaryTree<T>(value);
            else
                this.left.add(value);
        }
        else
        {
            if (this.right == null)
                this.right = new BinaryTree<T>(value);
            else
                this.right.add(value);
        }
    }
}

下面是递归函数看起来像的样子

    private void mirrorSymmetricTree(MirrorTreeNode<T> m, BinaryTreeNode<T> n)
    {
        if (n == null) // base case
        {
            return;
        }
        if (n.left != null)
        {
            m.left = new MirrorTreeNode<T>(n.left.value);
            mirrorSymmetricTree(m.left, n.left);
        }
        if (n.right != null)
        {
            m.right = new MirrorTreeNode<T>(n.right.value);
            mirrorSymmetricTree(m.right, n.right);
        }
    }
    public static MirrorTree mirrorSymmetricTree(BinaryTree<T> t)
    {
        if (t == null)
        {
            return null;
        }
        if (t.root != null)
        {
            this.root = new MirrorTreeNode<T>(t.root.value);
            mirrorSymmetricTree(this.root, t.root);
        }
        return this;
    }

MirrorTree节点看起来像这个

class MirrorTreeNode<T extends Comparable<T>>
{
    public T value;
    public MirrorTreeNode<T> left;
    public MirrorTreeNode<T> right;
    public MirrorTreeNode<T> (T value)
    {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    ..
}

然后，您可以通过在BinaryTree 上调用mirrorSymmetricTree来镜像树

BinaryTree<String> t1 = new  BinaryTree<>();
t1.addAll({"D","B","F","A","C","E","G"});
//            D
//        B       F
//      A   C   E   G
t1.printDFS();
// A, B, C, D, E, F, G
MirrorTree<String> t2 = new MirrorTree<>();
t2.mirrorSymmetricTree(t1);
// t2 is a copy of t1 now
t2.printDFS();
// A, B, C, D, E, F, G

票据

• 为了镜像大小为N的二叉树，您必须访问该树中的每个节点一次，因此镜像树的时间复杂度为O(N)

• 为了镜像二进制树，您存储的项目必须是Comparable，这意味着可以对它们进行比较，以确定是this.value > input还是this.value < input，从而决定将其放在树的何处

• 为了确保项目是Comparable，您可以手动实现，也可以要求模板类型必须实现Comparable<T>接口，这迫使T具有compareTo功能，可以将值\键作为数字进行比较，其中A.compareTo(B) > 0等同于A > B