二叉树的镜象

Question

假设有一棵树:

             1
            / \
           2   3
              / \
             4   5

然后镜像将是:

              1
             / \
            3   2
           / \
          5   4

假设节点具有以下结构:

struct node{
      node left;
      node right;
      int value;
}

有人可以建议一个算法吗？

Answer 1

听起来像是家庭作业.

看起来很容易.编写一个递归例程,深度优先访问每个节点,并构建左右反转的镜像树.

struct node *mirror(struct node *here) {

  if (here == NULL)
     return NULL;
  else {

    struct node *newNode = malloc (sizeof(struct node));

    newNode->value = here->value;
    newNode->left = mirror(here->right);
    newNode->right = mirror(here->left);

    return newNode;
  }
}

这将返回一个新树 - 其他一些答案就是这样做的.取决于你的任务要求你做什么:)

Answer 2

void swap_node(node n) {
  if(n != null) {
    node tmp = n.left;
    n.left = n.right;
    n.right = tmp;

    swap_node(n.left);
    swap_node(n.right);
  }
}

swap_node(root);

Answer 3

Banal解决方案:

for each node in tree
    exchange leftchild with rightchild.

Answer 4

JAVA中的递归和迭代方法:1)递归:

    public static TreeNode mirrorBinaryTree(TreeNode root){

    if(root == null || (root.left == null && root.right == null))
        return root;

    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

    mirrorBinaryTree(root.left);
    mirrorBinaryTree(root.right);


    return root;

}

2)迭代:

public static TreeNode mirrorBinaryTreeIterative(TreeNode root){
    if(root == null || (root.left == null && root.right == null))
        return root;

    TreeNode parent = root;
    Stack<TreeNode> treeStack = new Stack<TreeNode>();
    treeStack.push(root);

    while(!treeStack.empty()){
        parent = treeStack.pop();

        TreeNode temp = parent.right;
        parent.right = parent.left;
        parent.left = temp;

        if(parent.right != null)
            treeStack.push(parent.right);
        if(parent.left != null)
            treeStack.push(parent.left);
    }
    return root;
}