1.数据结构-树问题

前后中遍历-非递归写法

中序遍历稍微难一些,第二种写法不太好想出来

94. 二叉树的中序遍历

def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return None
        # 中序遍历写法1
        stack,ans = [root,],[]
        while(stack):
            while(root.left):
                stack.append(root.left)
                root = root.left
            node = stack.pop()
            ans.append(node.val)
            if node.right:
                stack.append(node.right)
                root = node.right
        # 中序遍历写法2 -> 写法1的升级写法，不需要赋值临时节点
        stack,ans = [],[]
        while(stack or root):
            while(root):
                stack.append(root)
                root = root.left
            root = stack.pop()
            ans.append(root.val)
            root = root.right

        return ans

中序遍历的应用
验证二叉搜索树，保底写法：遍历之后放到数组中，然后判断数组是否严格升序

98. 验证二叉搜索树

def isValidBST(self, root: TreeNode) -> bool:
        if not root: return True
        # 掌握中序法1写法
        stack,inorder = [root,],float('-inf')
        while(stack):
            while(root.left):
                stack.append(root.left)
                root = root.left
            node = stack.pop()
            if node.val <= inorder: return False
            inorder = node.val
            if(node.right):
                stack.append(node.right)
                root = node.right
        return True
        # 掌握中序法2写法
        stack, inorder = [], float('-inf')
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if root.val <= inorder:
                return False
            inorder = root.val
            root = root.right
        return True

590. N叉树的后序遍历

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if root is None:
            return []
        stack, res = [root, ], []
        while(stack):
            root = stack.pop()
            if(root is not None):
                res.append(root.val)
            for child in root.children:
                stack.append(child)
        return res[::-1]

BFS&层次遍历

使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。BFS总共有两个模板：

如果不需要确定当前遍历到了哪一层，BFS模板如下。

while queue 不空：
    cur = queue.pop()
    for 节点 in cur的所有相邻节点：
        if 该节点有效且未访问过：
            queue.push(该节点)

如果要确定当前遍历到了哪一层，BFS模板如下。
这里增加了level表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。

level = 0
while queue 不空：
    size = queue.size()
    while (size --) {
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未被访问过：
                queue.push(该节点)
    }
    level ++;

BFS经典例题1 - 129. 求根到叶子节点数字之和

思路：维护两个队列，一个是正常用的存储节点的，一个是节点的值方便用来做计算

def sumNumbers(self, root: TreeNode) -> int:
        if not root: return 0
        from collections import deque
        q1,q2 = deque([root]),deque([root.val]) 
        res = 0
        while(q1):
            node = q1.popleft()
            v = q2.popleft()
            l,r = node.left, node.right
            if l:
                q1.append(l)
                q2.append(v*10+l.val)
            if r:
                q1.append(r)
                q2.append(v*10+r.val)
            if not l and not r:
                res+=v
        return res

BFS经典例题2 - 116. 填充每个节点的下一个右侧节点指针

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        from collections import deque 
        q=deque([root])  
        while(q):
            size = len(q)
            for i in range(size):
                node = q.popleft()
                if i == size - 1:
                    node.next = None
                else:
                    node.next = q[0] #deque支持通过下标取元素
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return root

BFS经典例题 3 -127. 单词接龙

def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        size = len(beginWord)
        dic = defaultdict(list)
        for word in wordList:
            for i in range(size):
                key = word[:i]+"*"+word[i+1:]
                dic[key].append(word)
        from collections import deque
        q = deque()
        q.append((beginWord,1))
        visited = defaultdict(bool)
        visited[beginWord] = True
        while q:
            current_word,level = q.popleft()
            size = len(current_word)
            for i in range(size):
                key = current_word[:i]+'*'+current_word[i+1:]
                for neighour in dic[key]:
                    if neighour == endWord:
                        return level+1
                    if not visited[neighour]:
                        visited[neighour] = True
                        q.append((neighour,level+1))
        return 0

BFS经典例题4 - N叉树的层次遍历

def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root: return root
        d = collections.deque()
        d.append(root)
        res = []
        while d :
            n = len(d)
            tmp = []
            for i in range(n):
                node = d.popleft()
                tmp.append(node.val)
                if node.children:
                    d.extend(node.children)
            res.append(tmp)
        return res

递归遍历

面试题 04.02. 最小高度树

自己的代码

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
    if(len(nums)==0):
        return None
    mid = len(nums) // 2
    root = TreeNode()
    root.val = nums[mid]
    root.left = self.sortedArrayToBST(nums[0:mid])
    root.right = self.sortedArrayToBST(nums[mid+1:len(nums)])
    return root

下面是标准答案，可以看到一些细节上的差异

def sortedArrayToBST(self, nums: List[in]) -> TreeNode:
    if not len(nums):  return
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = self.sortedArrayToBST(nums[: mid]) 
    root.right = self.sortedArrayToBST(nums[mid + 1: ])
    return root

其他一些树的问题

二叉树深度

def maxDepth(self, root: TreeNode) -> int:
        if(root is None):
            return 0
        elif(root.left is None and root.right is None):
            return 1
        else :
            return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

二叉树镜像-递归

def mirrorTree(self, root: TreeNode) -> TreeNode:
        if(root is None):
            return 
        else:
            root.left, root.right = root.right, root.left
            self.mirrorTree(root.left)
            self.mirrorTree(root.right)
        return root

二叉搜索树所有节点值的和-递归

def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        if(root is None):
            return 0
        elif(root.val>=L and root.val<=R):
            l,r = 0,0
            if(root.left):
                l = self.rangeSumBST(root.left,L,R)
            if(root.right):
                r = self.rangeSumBST(root.right,L,R)
            return root.val + l + r

二叉树合并

def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:   
    if(not t1 and not t2):
        return None
    elif(t1 and not t2): 
        return t1
    elif(t2 and not t1):
        return t2
    else:
        t = TreeNode() 
        t.val = t1.val + t2.val
        t.left = self.mergeTrees(t1.left, t2.left)
        t.right = self.mergeTrees(t1.right, t2.right)
        return t

1.589. N叉树的前序遍历

def preorder(self, root: 'Node') -> List[int]:
       res = []
       def helper(root):
           if not root:
               return
           res.append(root.val)
           for child in root.children:
               helper(child)
       helper(root)
       return res

2. 108. 将有序数组转换为二叉搜索树

这个树的也不会

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None

            # 总是选择中间位置左边的数字作为根节点
            mid = (left + right) // 2

            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root

        return helper(0, len(nums) - 1)

下面的456分别是二叉树的三个遍历，重新复习一下吼吼吼

class Solution:
     # 前序遍历 根左右 让右边的后弹出，所以右边的要先压栈
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return None
        stack,ans = [root],[]
        while(stack):
            tmp = stack.pop()
            ans.append(tmp.val)
            if tmp.right:
                stack.append(tmp.right)
            if tmp.left:
                stack.append(tmp.left)
        return ans
  # 后序遍历 左右根 相当于根右左 然后取反就行 让左边的后弹出，所以左边的先压栈
  def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return None
        stack,ans = [root],[]
        while(stack):
            tmp = stack.pop()
            ans.append(tmp.val)
            if tmp.left:
                stack.append(tmp.left)
            if tmp.right:
                stack.append(tmp.right)
        return ans[::-1]
# 中序遍历 先把左节点全部入栈 弹出过程中查看是否有右节点
def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return None
        stack, ans = [root,],[]
        while(stack):
            while root.left:    
                stack.append(root.left)  
                root = root.left
            node = stack.pop()
            ans.append(node.val)
            if(node.right):
                stack.append(node.right)
                root = node.right
        return ans

1. 199. 二叉树的右视图

def rightSideView(self, root: TreeNode) -> List[int]:
        dic = {}
        max_depth = -1
        stack = [(root,0)]
        while(stack):
            #每次先弹出的是右边节点的值
            #没有右边节点就会弹出左边的，都没有表示没有节点了
            node, depth = stack.pop()
            if (node):
                max_depth = max(max_depth,depth)
                dic[depth] = dic.setdefault(depth,node.val)
                # 下面这两行代码换一下就可以从右视图变成左视图
                stack.append((node.left,depth+1))
                stack.append((node.right,depth+1))
        return list(dic.values())