【Leetcode】17.12: BiNode
2021/4/7 12:11:00
本文主要是介绍【Leetcode】17.12: BiNode,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
这题我最开始想直接用递归和二叉树的左小,右边大的性质,快速得解。左子树和右子树分别看作一条链表,然后讲左子树接在右子树的上面,而左子树当中的最大元素始终比右子树的最小元素要小。没想到代码竟然无法编译通过,错误解答如下:
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def convertBiNode(self, root: TreeNode) -> TreeNode: #这个题目直接使用中序遍历就可以了,我的递归方法居然不好使..是简单题也是有原因的 if root==None: return None else: node=self.convertBiNode(root.left) node_left=node while node!=None node.right!=None: node=node.right node.right=self.convertBiNode(root.right) root.right=node_left root.left=None
后来想到这题也就是简单难度的题目,只需要中序遍历inorder遍历就可以了,我醉了,,,这么简单。。最后用一个简单inoder遍历+一个数组储存得到的node变量,求解:
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def convertBiNode(self, root: TreeNode) -> TreeNode: new_node=TreeNode("0") cur=new_node ret=[] def DFS(root): if root==None: return None DFS(root.left) #引入中间变量 ret.append(root.val) DFS(root.right) DFS(root) for i in ret: new_node.right=TreeNode(i) new_node=new_node.right return cur.right
由于比起单个inorder遍历,时间复杂度从n变成了2n(不用大O表示法),在leetcode上排名不突出。因此尝试只用一个DFS的方法,看看能不能使用参数传递
这篇关于【Leetcode】17.12: BiNode的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升