题解 | #二叉树的镜像#

这个题目是对每个节点的左右子节点进行交换，实质上就是如何遍历树的所有节点，正好复习一遍树的遍历。

树的结构

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

解法一、递归后序遍历

public class Solution {
    public TreeNode Mirror (TreeNode root) {
        if (root == null) return null;
        TreeNode left = Mirror(root.left);
        TreeNode right = Mirror(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

解法二、层序BFS遍历

import java.util.*;
public class Solution {
    public TreeNode Mirror (TreeNode root) {
        if (root == null) return null;
        Queue<treenode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            processNode(node);

            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        return root;
    }

    private void processNode(TreeNode node) {
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
    }
}

解法三、先序非递归

import java.util.*;

public class Solution {
    public TreeNode Mirror(TreeNode root) {
        if (root == null)
            return null;
        Stack<treenode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode node = stack.pop();

            processNode(node);

            if (node.left != null)
                stack.push(node.left);
            if (node.right != null)
               stack.push(node.right);
        }
        return root;
    }

    private void processNode(TreeNode node) {
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
    }
}

解法四、中序非递归

import java.util.*;

public class Solution {
    public TreeNode Mirror(TreeNode root) {
    if (root == null)
        return null;
    Stack<treenode> stack = new Stack<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        if (!stack.isEmpty()) {
            node = stack.pop();

            processNode(node);

            // 注意这里以前是node.right，因为上面已经交换了，所以这里要改为node.left
            node = node.left;
        }
    }
    return root;
}

    private void processNode(TreeNode node) {
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
    }
}

解法五、后序非递归

import java.util.*;

public class Solution {
    public TreeNode Mirror(TreeNode root) {
    if (root == null)
        return null;
    Stack<treenode> stack1 = new Stack<>();
    Stack<treenode> stack2 = new Stack<>();
    TreeNode node = root;
    stack1.push(node);
    while (!stack1.isEmpty()) {
        node = stack1.pop();
        stack2.push(node);
        if (node.left != null) 
            stack1.push(node.left);
        if (node.right != null) 
            stack1.push(node.right);
    }
    while (!stack2.isEmpty()) {
        node = stack2.pop();
        processNode(node); // 实现对每个节点子节点的交换
    }
    return root;
}

    private void processNode(TreeNode node) {
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
    }
}