网络知识 娱乐 LeetCode - 翻转二叉树

LeetCode - 翻转二叉树

题目描述

一句话,翻转一棵二叉树。

原题备注:

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

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

解题思路:

我想应该有两种办法,第一种是递归,也是第一反应,第二种就是迭代。

递归法:先进行递归结束的条件判断。然后分别对左右子树进行递归,然后将左右子树互换位置即可。

迭代法:类似深度优先搜索的方式,采用队列存储未访问过的节点,分别将左右子树的节点进行位置互换,然后将节点的子节点存入队列。然后从队列中取出未访问的节点,进行翻转。每个节点只会进入一次队列,所以时间复杂度也是O(n)。

中文官网题解:

https://leetcode-cn.com/problems/invert-binary-tree/solution/

个人题解:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public TreeNode invertTree(TreeNode root) {        if(null == root)            return null;        else{            TreeNode left = invertTree(root.left);            TreeNode right = invertTree(root.right);            root.left = right;            root.right = left;            return root;        }    }}

结果:

简单,所以快。