题目地址
https://leetcode.com/problems/invert-binary-tree/description/
题目描述
Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
思路
遍历树(随便怎么遍历),然后将左右子树交换位置。
关键点解析
- 递归简化操作
- 如果树很高,建议使用栈来代替递归
- 这道题目对顺序没要求的,因此队列数组操作都是一样的,无任何区别
代码
- 语言支持:JS,Python,C++
Javascript Code:
/* * @lc app=leetcode id=226 lang=javascript * * [226] Invert Binary Tree * * https://leetcode.com/problems/invert-binary-tree/description/ * * algorithms * Easy (57.14%) * Total Accepted: 311K * Total Submissions: 540.6K * Testcase Example: '[4,2,7,1,3,6,9]' * * Invert a binary tree. * * Example: * * Input: * * * 4 * / \ * 2 7 * / \ / \ * 1 3 6 9 * * Output: * * * 4 * / \ * 7 2 * / \ / \ * 9 6 3 1 * * Trivia: * This problem was inspired by this original tweet by Max Howell: * * Google: 90% of our engineers use the software you wrote (Homebrew), but you * can’t invert a binary tree on a whiteboard so f*** off. * */ /** * 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; } };LeetCode题解199.binary-tree-right-side-view
题目地址 https://leetcode.com/problems/binary-tree-right-side-view/description/ 题目描述 Given a binary tree, imagine yourself standing on the right side of it, return the values of the no…
LeetCode题解124.binary-tree-maximum-path-sum题目地址 https://leetcode.com/problems/binary-tree-maximum-path-sum/description/ 题目描述 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as a…
LeetCode题解1104.path-in-zigzag-labelled-binary-tree题目地址 https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/description/ 题目描述 在一棵无限的二叉树上,每个节点都有两个子节点,树中的节点 逐行 依次按 “之” 字形进行标记。 如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标…
LeetCode题解145.binary-tree-postorder-traversal题目地址 https://leetcode.com/problems/binary-tree-postorder-traversal/description/ 题目描述 Given a binary tree, return the postorder traversal of its nodes' values. For example: Given bi…
LeetCode题解144.binary-tree-preorder-traversal题目地址 https://leetcode.com/problems/binary-tree-preorder-traversal/description/ 题目描述 Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null…