【leetcode】二叉树（汇总2）

101. 对称二叉树 

class Solution: def isSymmetric(self, root: TreeNode) -> bool: def check(node1, node2): if not node1 and not node2: return True elif not node1 or not node2: return False if node1.val != node2.val: return False return check(node1.left, node2.right) and check(node1.right, node2.left) return check(root, root) # 其实就是层序遍历，然后检查每一层是不是回文数组 class Solution(object): def isSymmetric(self, root): queue = [root] while(queue): next_queue = list() layer = list() for node in queue: if not node: layer.append(None) continue next_queue.append(node.left) next_queue.append(node.right) layer.append(node.val) if layer != layer[::-1]: return False queue = next_queue return True

235. 二叉搜索树的最近公共祖先

# 二叉搜索树，右边节点比他大，左边节点比他小 # 递归寻找，若p,q都小于跟结点，递归去左子树找，若p,q都大于根节点，递归去右子树找，一大一小就是根节点 class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': while root: if root.val > p.val and root.val > q.val: root = root.left elif root.val < p.val and root.val < q.val: root = root.right else: return root return None # 没看懂 class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if root==None or root==p or root==q: return root else: lchild=self.lowestCommonAncestor(root.left,p,q) rchild=self.lowestCommonAncestor(root.right,p,q) if lchild==None: return rchild elif rchild==None: return lchild else: return root