操作给定的二叉树,将其变换为源二叉树的镜像。 输入描述: 二叉树的镜像定义:

源二叉树:

            8
           /  \
          6    10
         / \   / \
       5    7 9   11

镜像二叉树:

             8
           /  \
          10   6
         / \  / \
       11   9 7  5
package tree;

import common.TreeNode;

import java.util.Stack;

public class 二叉树的镜像 {
    /**
     * 自想1:
     * 递归地进行对称变换
     */
    public void Mirror1(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        Mirror1(root.left);
        Mirror1(root.right);
    }

    /**
     * 讨论区:
     * 用栈来代替递归
     * 处理 ->下一次要处理的结点入栈里 -> 弹出进行下一次变换
     */
    public void Mirror2(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur.left != null || cur.right != null) {
                // 交换
                TreeNode tmp = cur.left;
                cur.left = cur.right;
                cur.right = tmp;
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
        }
    }
}

results matching ""

    No results matching ""