Java实现 LeetCode 226 翻转二叉树

226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

     4

   /   \

  2     7

 / \   / \

1   3 6   9

输出：

     4

   /   \

  7     2

 / \   / \

9   6 3   1

备注:

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

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

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

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

 * }

 */

class Solution {

         // 先序遍历--从顶向下交换

        // public TreeNode invertTree(TreeNode root) {

        //     if (root == null) return null;

        //     // 保存右子树

        //     TreeNode rightTree = root.right;

        //     // 交换左右子树的位置

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

        //     root.left = invertTree(rightTree);

        //     return root;

        // }

//中序遍历

//  public TreeNode invertTree(TreeNode root) {

//             if (root == null) return null;

//             invertTree(root.left); // 递归找到左节点

//             TreeNode rightNode= root.right; // 保存右节点

//             root.right = root.left;

//             root.left = rightNode;

//             // 递归找到右节点 继续交换 : 因为此时左右节点已经交换了,所以此时的右节点为root.left

//             invertTree(root.left);

//     }

//后序遍历

//  public TreeNode invertTree(TreeNode root) {

//             // 后序遍历-- 从下向上交换

//             if (root == null) return null;

//             TreeNode leftNode = invertTree(root.left);

//             TreeNode rightNode = invertTree(root.right);

//             root.right = leftNode;

//             root.left = rightNode;

//             return root;

//         }

//层次遍历

 public TreeNode invertTree(TreeNode root) {

            // 层次遍历--直接左右交换即可

            if (root == null) return null;

            Queue<TreeNode> queue = new LinkedList<>();

            queue.offer(root);

            while (!queue.isEmpty()){

                TreeNode node = queue.poll();

                TreeNode rightTree = node.right;

                node.right = node.left;

                node.left = rightTree;

                if (node.left != null){

                    queue.offer(node.left);

                }

                if (node.right != null){

                    queue.offer(node.right);

                }

            }

            return root;

        }

}

巴特西

Java实现 LeetCode 226 翻转二叉树

226. 翻转二叉树

最新文章

热门文章