镜像二叉树

一份执着✘

发布于 2018-06-04 16:56:14

6440

发布于 2018-06-04 16:56:14

文章被收录于专栏：赵俊的Java专栏

题意

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

样例

二叉树的镜像定义：源二叉树

思路

递归法

递归的终止条件就是当前树为 null 或该树的左子树与右子树都为 null。
递归操作是交换当前数的左右子树。
递归条件：

当前数的左子树不为空时对左字树进行递归操作。
当前数的右子树不为空时对右子树进行递归操作。

模拟压栈法

既然递归的原理是通过压栈实现的，那么我们也可以自己来创建一个栈来模拟实现。

先将根节点放入栈中，然后开始循环，循环条件是栈不为空，将栈顶元素出栈，当该节点的左子树或右子树不为空，就将左右子树进行交换，然后当左子树不为空时，将左子树压栈，当右子树不为空时，将右子树压栈。如此循环，直到栈为空。

代码实现

递归法

/**
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 temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        if (root.left != null)
            Mirror(root.left);
        
        if (root.right != null)
            Mirror(root.right);
    }
}

模拟压栈法

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}
*/
import java.util.Stack;
public class Solution {
    //模拟递归的压栈法
    public void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode node =  stack.pop();
            if (node.left != null || node.right != null) {
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
            }
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right); 
        }
    }
}