【Leetcode】二叉树问题整理笔记 之 普通遍历取值

Overview

遍历二叉树257. Binary Tree Paths - 输出二叉树所有根到叶的路径94. Binary Tree Inorder Traversal -- 中序遍历144. Binary Tree Preorder Traversal -- 前序遍历145. Binary Tree Postorder Traversal - 后序遍历538. Convert BST to Greater Tree - 中序遍历变体问题965. Univalued Binary Tree - 判断一棵二叉树是否只含有一个值993. Cousins in Binary Tree - 判断深度与父节点 遍历叶子节点872. Leaf-Similar Trees Reference

---

遍历二叉树

257. Binary Tree Paths - 输出二叉树所有根到叶的路径

Solution:

class Solution: def get_bt_paths(self, root): if root.left is None and root.right is None: return [[root.val]] me = root ret = [] if root.left: for path in self.get_bt_paths(root.left): path.append(me.val) ret.append(path) if root.right: for path in self.get_bt_paths(root.right): path.append(me.val) ret.append(path) return ret def binaryTreePaths(self, root: TreeNode) -> List[str]: if root is None: return [] all_paths = self.get_bt_paths(root) ret = [] for path in all_paths: ret.append("->".join([str(_) for _ in reversed(path)])) return ret

94. Binary Tree Inorder Traversal – 中序遍历

Solution:

class Solution: def recursive_inorder_traversal(self, root): if root is None: return [] left = self.recursive_inorder_traversal(root.left) middle = root.val right = self.recursive_inorder_traversal(root.right) ret = left ret.append(middle) ret.extend(right) return ret def iterative_inorder_traversal(self, root): if root is None: return [] ret = [] stack = [] dummy_root = TreeNode(None) dummy_root.right = root DO = True curr = dummy_root while DO or curr.right or stack: if DO: # for "do{...}while();" DO = False if curr.right: curr = curr.right while curr.left: stack.append(curr) curr = curr.left elif stack: curr = stack.pop() ret.append(curr.val) return ret def inorderTraversal(self, root: TreeNode) -> List[int]: # return self.recursive_inorder_traversal(root) return self.iterative_inorder_traversal(root)

第一次是递归的方式，速度比较常规。 第二次提交使用迭代的方式，发现运行速度比较快 - faster than 99%+ submissions

144. Binary Tree Preorder Traversal – 前序遍历

前序遍历：先取节点值，再分别取左右子树的值。

class Solution: def recursive_preorder_traversal(self, root): if root is None: return [] ret = [root.val] ret.extend(self.recursive_preorder_traversal(root.left)) ret.extend(self.recursive_preorder_traversal(root.right)) return ret def iterative_preorder_traversal(self, root): if root is None: return [] ret = [] stack = [] DO = True curr = root while DO or curr or stack: if DO: # for "do{...}while();" DO = False if curr: while curr: ret.append(curr.val) stack.append(curr.right) curr = curr.left elif stack: curr = stack.pop() return ret def preorderTraversal(self, root: TreeNode) -> List[int]: # return self.recursive_preorder_traversal(root) return self.iterative_preorder_traversal(root)

先做递归的 solution submit，后一个是迭代的 solution submit。

145. Binary Tree Postorder Traversal - 后序遍历

后序遍历：先分别取左右子节点值，最后取当前节点值

2020/07/10

这一题不知道为什么被算为 hard。

Solution:

递归解法（十分简单）：class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: def recursive(anode): if anode is None: return [] ans = (recursive(anode.left)) ans.extend(recursive(anode.right)) ans.append(anode.val) return ans return recursive(root) 只要将“当前”节点的 value 在最后放入 answer 列表之中就可以了。迭代解法：class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: if root is None: return [] stack = [] ans = [] def do_expand(anode): if isinstance(anode, TreeNode): stack.append(anode.val) stack.append(anode.right) stack.append(anode.left) do_expand(root) while stack: last = stack.pop() if isinstance(last, int): ans.append(last) elif last is None: continue elif isinstance(last, TreeNode): do_expand(last) return ans

迭代遍历取值的写法比我上面 144. 的前序遍历和 94. 的中序遍历的迭代取值的方案要简洁地多，而且也比较好理解。我想可能是因为多做一些题，解决这类问题更熟练了。

迭代的思路是，不断地 .pop “缓存”队列的最后一个值，如果这个值是“子节点”，就对它以“前序遍历”或“中序遍历”或“后序遍历”的定义进行“拓展” 。 不断地拓展、.pop、再拓展、再 .pop 最终就能遍历完。 以[1,null,2,3] 为例（这个输入到 leetcode 中去可视化，就不截图了）； 算法运行过程 stack 地变化如下：

[(1: TreeNode), ] # expand [(1: int), (2: TreeNode), (NULL), ] # continue [(1: int), (2: TreeNode), ] # expand [(1: int), (2: int), (NULL), (3: TreeNode)] # expand [(1: int), (2: int), (NULL), (3: int) (NULL) (NULL)] # continue [(1: int), (2: int), (NULL), (3: int) (NULL),] # continue [(1: int), (2: int), (NULL), (3: int), ] # ans.append(last) ans: [3] [(1: int), (2: int), (NULL), ] # continue [(1: int), (2: int), ] # ans.append(last) ans: [3, 2] [(1: int), ] # ans: [3, 2, 1]

这个算法从我个人角度应该算是迭代解法地终极形式了，因为非常好理解，然后三种遍历方式都可以用，调整 expand 函数内部的顺序就是三种遍历方式的实现了。

538. Convert BST to Greater Tree - 中序遍历变体问题

Solution:

在解决方案上，这其实是一个中序遍历的变体。 先遍历到当前 root 节点的最右节点，然后一步一步往小于它的值增加。返回值是当前 root 节点的最左节点的最终值。

class Solution: def recursive(self, root: TreeNode, greater_sum: int) -> int: if root is None: return greater_sum sum_of_right = self.recursive(root.right, greater_sum) val = root.val + sum_of_right root.val = val sum_of_left = self.recursive(root.left, val) return sum_of_left def convertBST(self, root: TreeNode) -> TreeNode: if root is None: return None self.recursive(root, 0) return root

965. Univalued Binary Tree - 判断一棵二叉树是否只含有一个值

Solution:

class Solution: def is_all_the_same_val(self, root, key): if root is None: return True if root.val == key: return self.is_all_the_same_val(root.left, key) and self.is_all_the_same_val(root.right, key) return False def isUnivalTree(self, root: TreeNode) -> bool: if root is None: return True key = root.val return self.is_all_the_same_val(root, key)

993. Cousins in Binary Tree - 判断深度与父节点

Solution:

class Solution: def recursive(self, root, depth, key): if root is None or root.val == key: raise RuntimeError("shouldn't run here") depth += 1 ret = False if root.left: if root.left.val == key: ret = (root, depth + 1) else: ret = self.recursive(root.left, depth, key) if ret is False: if root.right: if root.right.val == key: ret = (root, depth + 1) else: ret = self.recursive(root.right, depth, key) return ret def isCousins(self, root: TreeNode, x: int, y: int) -> bool: if root is None or root.val in (x, y): return False try: x_parent, x_depth = self.recursive(root, 0, x) y_parent, y_depth = self.recursive(root, 0, y) if x_depth == y_depth and x_parent is not y_parent: return True except Exception: return False return False

在提交之后，看到这个对比速度，我又考虑了一下有没有更快的办法。 然后想起来，如果按层遍历的化，应该速度会快很多。不过这题不难，就不改了。

---

遍历叶子节点

872. Leaf-Similar Trees

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Solution:

class Solution: def recursive_traversal(self, root): ret = [] if root.left: ret.extend(self.recursive_traversal(root.left)) if root.right: ret.extend(self.recursive_traversal(root.right)) if root.left is None and root.right is None: return [root.val] return ret def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool: if root1 and root2: root1_vals = self.recursive_traversal(root1) root2_vals = self.recursive_traversal(root2) return root1_vals == root2_vals if root1 is None and root2 is None: return True return False

---

Reference

---