Skip to content

Latest commit

 

History

History
172 lines (138 loc) · 3.68 KB

226.invert-binary-tree.md

File metadata and controls

172 lines (138 loc) · 3.68 KB
Raw

题目地址(226. 翻转二叉树)

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

题目描述

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：

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

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这是一个经典的面试问题，难度不大，大家可以用它练习一下递归和迭代。

算法：

遍历树（随便怎么遍历），然后将左右子树交换位置。

关键点解析

  • 递归简化操作
  • 如果树很高，建议使用栈来代替递归
  • 这道题目对顺序没要求的，因此队列数组操作都是一样的，无任何区别

代码

  • 语言支持：JS，Python，C++

Javascript Code:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
  if (!root) return root;
  // 递归
  //   const left = root.left;
  //   const right = root.right;
  //   root.right = invertTree(left);
  //   root.left = invertTree(right);
  // 我们用stack来模拟递归
  // 本质上递归是利用了执行栈，执行栈也是一种栈
  // 其实这里使用队列也是一样的，因为这里顺序不重要

  const stack = [root];
  let current = null;
  while ((current = stack.shift())) {
    const left = current.left;
    const right = current.right;
    current.right = left;
    current.left = right;
    if (left) {
      stack.push(left);
    }
    if (right) {
      stack.push(right);
    }
  }
  return root;
};

Python Code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        stack = [root]
        while stack:
            node = stack.pop(0)
            node.left, node.right = node.right, node.left
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return root

C++ Code：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        auto q = queue<TreeNode*>();
        q.push(root);
        while (!q.empty()) {
            auto n = q.front(); q.pop();
            swap(n->left, n->right);
            if (n->left != nullptr) {
                q.push(n->left);
            }
            if (n->right != nullptr) {
                q.push(n->right);
            }
        }
        return root;
    }
};

复杂度分析

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。