「二叉树」专题 2:反转一棵二叉树


「二叉树」专题 2:反转一棵二叉树

注:这一节练习 3 和练习 4 都是很经典的问题。

和二叉树相关的问题,在面试中是非常常见的。一旦我们熟悉了这些问题以后,会发现这些问题其实是非常简单的。

「力扣」第 226 题:反转一棵二叉树

翻转一棵二叉树。

示例:

输入:

4
/   \
2     7
/ \   / \
1   3 6   9

输出:

4
/   \
7     2
/ \   / \
9   6 3   1

备注:
这个问题是受到 Max Howell 原问题 启发的 :

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。

分析:算法是非常重要的基本功。即使是大公司都非常注重基础问题的考察。

这道问题可以说是一个经典的问题。LeetCode 上有如下备注:

这个问题是受到 Max Howell 的 原问题 启发的 :

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。

思路1:我们可以使用递归方法来完成,我们写好之后,会发现其实就是完成了一次深度优先遍历,并且是前序遍历,有的朋友可能写出来的后序遍历,那么我们不禁要问,中序遍历可不可以,答案是不可以,因为中序遍历很可能一个结点会被翻转两次,这与我们的要求是违背的。

Java 代码:

LeetCode 第 226 题:反转一棵二叉树

Java 代码:后序遍历

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        // swap root.left 和  root.right
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}

Java 代码:与上面的代码等价

public class Solution2 {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = invertTree(right);
        root.right = invertTree(left);
        return root;
    }
}

方法一:前序遍历

Java 代码:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        // 左子树和右子树交换,即使左右子树都空也不影响正确性
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // 递归翻转左右子树
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

方法二:中序遍历

注意:写中序遍历的时候,不能仅仅只是将前序遍历的代码顺序调整一下。

因为在“中序遍历”的时候,左右子树已经交换过了,因此原来写 invertTree(root.right); 的地方,应该写作 invertTree(root.left);

Java 代码:

public class Solution {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        invertTree(root.left);

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

        // 注意:因为左右子树已经交换了,因此这里不能写 invertTree(root.right);
        invertTree(root.left);
        return root;
    }
}

方法三:后序遍历

Java 代码:

public class Solution {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        invertTree(root.left);
        invertTree(root.right);

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

方法四:层序遍历

Java 代码:

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    public TreeNode invertTree(TreeNode root) {
        // 结点为空的特殊情况要先考虑
        if (root == null) {
            return null;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            // 只要其中之一非空,我都交换,并且把非空的结点添加到队列里
            if (curNode.left != null || curNode.right != null) {
                // 先翻转
                TreeNode temp = curNode.left;
                curNode.left = curNode.right;
                curNode.right = temp;
                // 把非空的节点加入队列
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }
        }
        return root;
    }
}

image-20181214103339221


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
下一篇 
「树」专题 1:树与递归 「树」专题 1:树与递归
「树」专题 1:树与递归 树是理解「递归」和「分治」算法的很好的数据结构; 很多高级数据结构都是从「树」来的。 我们开始介绍「二叉树和递归」。递归,是使用计算机解决问题的一种重要的思考方式。而二叉树由于其天然的递归结构,使得基于二叉树的算
  目录