读前福利:几百本互联网技术书籍送给大家https://mp.weixin.qq.com/s/dFqVQ2qJxvQ0YrIlPISJuw

每天分享一个LeetCode题目
每天 5 分钟,一起进步!
LeetCode 中序遍历,地址:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
树结点类
1 2 3 4 5
| class TreeNode(object): def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
|
递归遍历
递归遍历通常来说代码形式比较简单和整洁,非常易读。
但是理解起来不是那么容易,然而递归思想对于整个树相关的题目部分是相对比较重要的,因为,递归的思路在很多的题目中很容易就可以进行解决!
1 2 3 4 5 6 7 8 9 10 11
| def inorderTraversal(self, root): def in_order(root): if not root: return in_order(root.left) res.append(root.val) in_order(root.right)
res = [] in_order(root) return res
|
非递归遍历
非递归遍历,也是要借助【栈】来进行实现的
1.不断访问左孩子,压栈,直到被访问的左孩子为空
2.从栈顶弹出结点并且访问,随后访问右孩子,如果右孩子为空,则从栈顶弹出结点并且访问。否则,继续执行第 1 点
3.直到栈为空并且被访问的右孩子也为空
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| def inorderTraversal_no_recursion(self, root): if not root: return [] stack = [] res = [] while stack or root: while root: stack.append(root) root = root.left if stack: tmp = stack.pop() res.append(tmp.val) root = tmp.right return res
|
完整代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
|
class TreeNode(object): def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
class Solution(object): def inorderTraversal(self, root): def in_order(root): if not root: return in_order(root.left) res.append(root.val) in_order(root.right)
res = [] in_order(root) return res
def inorderTraversal_no_recursion(self, root): if not root: return [] stack = [] res = [] while stack or root: while root: stack.append(root) root = root.left if stack: tmp = stack.pop() res.append(tmp.val) root = tmp.right
return res
if __name__ == "__main__": root = TreeNode('A') node_B = TreeNode('B') node_C = TreeNode('C') node_D = TreeNode('D') node_E = TreeNode('E') node_F = TreeNode('F') node_G = TreeNode('G') node_H = TreeNode('H') node_I = TreeNode('I') root.left, root.right = node_B, node_C node_B.left, node_B.right = node_D, node_E node_C.left, node_C.right = node_F, node_G node_D.left, node_D.right = node_H, node_I
s = Solution() print(s.inorderTraversal(root)) print(s.inorderTraversal_no_recursion(root))
|
最后
在这里给大家准备了几百本的互联网技术类书籍,需要的来下载吧!点击获取
有任何问题,欢迎随时交流!!!