秋叶红霜CCCCCC

分类

/ 注册

全部文章（共47篇）

题解 | #对称的二叉树#

python3，非递归方法，对称性，对应着回文性。对左右子树分别做层次遍历，各自维护一个栈，因为对称性对应着回文性，所以入栈的顺序变一下，则对称性必会导致栈相同，如果不同则无对称性 class Solution: def isSymmetrical(self , pRoot: TreeNod...

Python3

2022-10-28

0 224

题解 | #二叉树中和为某一值的路径(三)#

python3 DFS + 哈希表，双O(n)复杂度。利用哈希表维护：从根出发的路径和及其对应的条数。当前节点，如果是这样的情况：当前累加和temp - 目标和sum 在哈希表出现，则意味着出现了累加和sum，累加和sum的条数就是temp - sum的条数。如果没出现temp ...

Python3

2022-10-28

0 238

题解 | #序列化二叉树#

序列化和反序列化，意味着做一个可逆变换。可逆变换也就是一一映射，保留所有的原始信息，都要序列化。用层次遍历。序列化的时候：注意数值转换为字符。反序列化的时候：逐次遍历字符串解绑后的数组，对栈循环，数组是none，就不操作，不是none就作为栈弹出的结点的左结点或...

Python3

2022-10-27

0 256

题解 | #序列化二叉树#

很骚的方法，能过测例。虽然不是出题的目的。 class Solution: def Serialize(self, root): &n...

Python3

2022-10-27

0 235

题解 | #二叉树的下一个结点#

python3，非递归法。利用中序遍历的性质：如果有右结点，中序遍历下一个就是右结点如果没有右结点：如果有父结点，且是父结点的左结点，返回父结点。如果有父结点，且是父结点的右结点，则循环继续向上，寻找一...

Python3

2022-10-27

0 232

题解 | #判断是不是平衡二叉树#

Python3递归。所谓自底向上，就是利用非平衡的传染性：有非平衡子树，自己一定非平衡。所以只要子树出现非平衡，就返回-1（非正常深度，正常的深度>=0），子树都平衡，才计算高度差并返回 class Solution: # ...

Python3

2022-10-27

0 251

题解 | #判断是不是平衡二叉树#

python3，递归 class Solution: def IsBalanced_Solution(self , pRoot: TreeNode) -> bool: &n...

Python3

2022-10-27

0 241

题解 | #二叉搜索树与双向链表#

python3，典型的中序遍历中序遍历，两个指针记录前驱结点和后驱结点，递归后驱结点，为空时前驱结点到达尾部（即最大/最右）。如果要求做成循环列表，额外连上首尾即可。 class Solution: def Conver...

Python3

2022-10-27

0 265

题解 | #二叉树中和为某一值的路径(二)#

Python3 深度优先搜索，维护一个路径列表。如果规定了结点值的正负性，还可以剪枝。否则，这里只能递归到叶子结点了。叶子节点且满足和的条件，把path加入res结果集。满足不满足，都要把节点踢出path，以便其他路径的递归。 class Solution: &...

Python3

2022-10-27

0 239

题解 | #二叉搜索树的后序遍历序列#

python3，时间复杂度O(n)的非递归方法。 BST的后序遍历是左右中，逆序后序遍历，就变成了中右左。BST的性质，右一定是大于中的，左一定是小于中的。设置一个比较参数root，初始化是无穷大。根部先入栈，如果元素比栈顶大，则是右结点（root是不允许出现左结点后再出现右结...

Python3

2022-10-27

0 231