leetcode刷题实录|leetcode226 翻转二叉树

【leetcode刷题实录|leetcode226 翻转二叉树】labuladong
二叉树题目的一个难点就是,如何把题目的要求细化成每个节点需要做的事情。
写树相关的算法,简单说就是,先搞清楚当前 root 节点该做什么,然后根据函数定义递归调用子节点,递归调用会让孩子节点做相同的事情。
题目链接: leetcode226 翻转二叉树
解题基础: 二叉树遍历框架
本题思路: 只要把二叉树上的每一个节点的左右子节点进行交换,最后的结果就是完全翻转之后的二叉树。
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的原子性语法可以在一句话中交换值,所以三句话缩写成了一句话 总结:如果你想拆开写,必须写三句,且用临时变量暂存

    推荐阅读