翻转二叉树

题目描述

力扣链接🔗

题目分析

大概思路为每次遍历道一个节点交换2个左右孩子节点。具体代码中详细注释。

代码

以下所有方法交换左右孩子节点的方法都为

/**
 * 用于交换两个节点
 *
 * @param root
 */
public void wrapNode(TreeNode root) {
    TreeNode tempNode = root.left;
    root.left = root.right;
    root.right = tempNode;
}

以下代码就不详细写了。

递归法

前后序递归

/**
 * 前序和后序的递归遍历
 *
 * @param root
 * @return
 */
public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    wrapNode(root);
    // 递归遍历(前序和后序都可以) 后序交换顺序即可
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

中序递归法

不是严格的中序遍历，因为此处没有取值，所以普通递归而可以使用。

/**
 * 中序递归法（不完全是中序）
 *
 * @param root
 * @return
 */
public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    invertTree(root.left);  // 左
    wrapNode(root);         // 中
    invertTree(root.left);  // 左，此时已经翻转，相当于现在左边是右孩子
    return root;
}

统一迭代遍历

中序的迭代遍历

/**
 * 统一迭代的中序遍历
 *
 * @param root
 * @return
 */
public TreeNode invertTree(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return null;
    }
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.peek();
        if (node != null) {
            stack.pop();    // 先出栈，防止重复
            if (node.right != null) stack.push(node.right);
            stack.push(node);
            stack.push(null);
            if (node.left != null) stack.push(node.left);
        } else {
            stack.pop();    // 将null出栈
            node = stack.peek();
            stack.pop();
            wrapNode(node);
        }
    }
    return root;
}

层序遍历

层序遍历也是每层遍历到一个节点就进行翻转。

/**
* 层序遍历
*
* @param root
* @return
*/
public TreeNode invertTree(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    if (root == null) {
        return null;
    }
    queue.offer(root);
    while (!queue.isEmpty()) {
        int len = queue.size();
        while (len > 0) {
            TreeNode node = queue.poll();
            wrapNode(node);    // 直接交换孩子节点即可
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            len--;
        }
    }
    return root;
}