一天一大 lee(翻转二叉树)难度:简单-Day20200916
题目:[1]
翻转一棵二叉树。
示例：
4
/ \
2 7
/ \ / \
1 3 6 9
输出
4
/ \
7 2
/ \ / \
9 6 3 1
抛砖引玉
抛砖引玉
思路
深度优先遍历（DFS）
- 传入的节点如果不是叶子节点即包含左右子树，则优先翻转左右子树
- 递归到叶子节点开始翻转，之后向上逐层交换拼接
/**
* 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 === null) {
return null
}
let left = invertTree(root.left),
right = invertTree(root.right)
root.left = right
root.right = left
return root
}
广度优先遍历（BFS）
- 从根结点到叶子节点逐层入栈
- 从栈内逐个取出翻转，遇到非叶子节点继续入栈
/**
* 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) {
let queue = [root]
while (queue.length) {
let node = queue.shift()
if (node) {
let left = node.left
node.left = node.right
node.right = left
queue.push(node.left)
queue.push(node.right)
}
}
return root
}
举报
腾讯云开发者
