【leetcode刷题实录|leetcode226 翻转二叉树】labuladong题目链接: leetcode226 翻转二叉树
二叉树题目的一个难点就是,如何把题目的要求细化成每个节点需要做的事情。
写树相关的算法,简单说就是,先搞清楚当前root
节点该做什么,然后根据函数定义递归调用子节点,递归调用会让孩子节点做相同的事情。
解题基础: 二叉树遍历框架
本题思路: 只要把二叉树上的每一个节点的左右子节点进行交换,最后的结果就是完全翻转之后的二叉树。
Java版
/**
* 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) {
// base case
if (root == null) {
return null;
}/**** 前序遍历位置 ****/
// root 节点需要交换它的左右子节点
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 让左右子节点继续翻转它们的子节点
invertTree(root.left);
invertTree(root.right);
return root;
}
}
Python版
# Definition for a binary tree node.
# class TreeNode:
#def __init__(self, x):
#self.val = x
#self.left = None
#self.right = Noneclass Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
root.left,root.right=self.invertTree(root.left),self.invertTree(root.right)
return root
问题收录:
- 类方法必须包含参数
self
,且为第一个参数,self
代表的是类的实例
- self 代表的是类的实例
-
->
常常出现在python函数定义的函数名后面,为函数添加元数据,描述函数的返回类型
- 给函数参数增加元信息
- 请问
root.left,root.right=self.invertTree(root.right),self.invertTree(root.left)
把这一行,拆分为2行root.left = self.invertTree(root.right)
、root.right = self.invertTree(root.left)
写,为什么结果不一样啊
-
拆两行写的话,你第二行的root.left已经不是原来的root.left了
-
你要想拆开写也可以,必须建立一个临时的节点暂存原来的节点 就类似你想让两个变量a,b交换值,你就必须先创建一个temp暂存a: temp = a ; a= b; b= temp 因为python的原子性语法可以在一句话中交换值,所以三句话缩写成了一句话 总结:如果你想拆开写,必须写三句,且用临时变量暂存
-
推荐阅读
- LeetCode 226翻转二叉树
- 数组|二、数据结构与算法 稀疏数组
- 刷题|leetcode226翻转二叉树(JAVA版)
- leetcode|LeetCode226翻转二叉树(递归)
- 二叉树|leetcode 226 翻转二叉树
- 算法学习|最近公共祖先之树上倍增求法
- 蓝桥杯|蓝桥杯素数(二)
- java|springboot缓存+springboot整合redis缓存
- java|SpringBoot整合Redis以及Redis缓存