0%

机试——二叉树遍历

发表于 更新于 阅读次数： Valine：
本文字数： 884 阅读时长 ≈ 1 分钟

​ 二叉树最常用的遍历算法主要分为下面几种：

​ 1.先序遍历

​ 2.中序遍历

​ 3.后序遍历

​ 4.层次遍历

​ 下面我们将针对这些遍历算法的递归与非递归实现分别给出代码实现以及特点。

这里有一点我们需要注意:

​ 无论是前序、中序、后续，都是指根节点访问的顺序，而左右节点的相对访问顺序永远是相同的，即先访问做节点，后访问右节点。

先序遍历

​ 先序遍历指在二叉树遍历过程中首先输出根节点，然后再分别输出左右节点的遍历方式。

递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        def core(result,root):
            if root==None:
                return 
            result.append(root.val)
            core(result,root.left)
            core(result,root.right)
        
        result = []
        core(result,root)
        return result
非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root==None:
            return []
        
        res = []
        stack = [root]
        
        while stack:
            node = stack.pop()
            res.append(node.val)
            #注意这里的顺序一定是先右后左，和一般的相反
            if node.right!=None:
                stack.append(node.right)
            if node.left!=None:
                stack.append(node.left)
        
        return res

中序遍历

​ 二叉树的中序遍历是指现先遍历左节点，中间遍历根节点，最后在遍历右节点的便利方式。

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def Core(root):
            if root==None:
                return []
            
            Core(root.left)
            result.append(root.val)
            Core(root.right)
            
            return result
        
        result = []
        Core(root)
        
        return result

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root==None:
            return []
        
        stack = []
        result = []
        
        pos = root
        
        while stack or pos:
            if pos:
                stack.append(pos)
                pos = pos.left
            else:
                pos = stack.pop()
                result.append(pos.val)
                pos = pos.right
        return result

后序遍历

层次遍历

非递归实现

​ 利用队列先进先出的特点，依次将结点的左、右孩子入队，然后依次出队访问，以此为循环。当有些题目中要求按照层输出时，需要根据每层的节点个数做一个计数。

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
def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        
        queue = [root]
        result = []
        
        while queue:
            tmp = []
            number_flag = len(queue)   #层节点个数计数器
            i = 0
            while i<number_flag:
                node = queue.pop(0)
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                i += 1
            result.append(tmp)
        
        return result

根据两个序列复原二叉树

​ 这种题目其实只有两个，核心是找出先根据一个序列找出根节点，然后在根据另一个序列找出其左右子树的元素，然后不断的递归这个过程即可。

已知前序遍历中序遍历

​ 在已知前序遍历的题目中，就以前序遍历为基础，去不断地区分剩下的数据应该在左子树还是右子树即可

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
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
				"""
					先将前序遍历的第一个节点作为根节点，然后在后序遍历中找到其对应的位置，左右分别做相同的操作
				"""
        len_pre = len(preorder)
        len_in = len(inorder)
        
        if len_pre==0 or len_in==0:
            return None
        
        
        tree_root = TreeNode(preorder[0])
        preorder = preorder[1:]
        
        
        left_len = 0
        for i in inorder:
            if i==tree_root.val:
                break
            else:
                left_len+=1
        inorder.remove(tree_root.val)
        if left_len>=1:
            tree_root.left =  self.buildTree(preorder[:left_len],inorder[:left_len])
        if len(preorder)-left_len>=1:
            tree_root.right = self.buildTree(preorder[left_len:],inorder[left_len:])
        
        return tree_root
已知前序遍历和后序遍历
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
def constructFromPrePost(self, pre, post):
        """
        :type pre: List[int]
        :type post: List[int]
        :rtype: TreeNode
        """
        """
            前序遍历的第一个节点必定是根节点，随后的节点就是其左子树的根节点，然后再在
        后序遍历中找到这个节点的位置就可以确定左子树中有哪些节点，右子树中有哪些节点
        """
        
        tree_root = TreeNode(pre[0])
        
        pre = pre[1:]
        post = post[:-1]
        left_len = 0
        
        for i in post:
            if i==pre[0]:
                left_len+=1
                break
            else:
                left_len+=1
        
        if left_len>=1:
            tree_root.left = self.constructFromPrePost(pre[:left_len],post[:left_len])
        if len(post)-left_len>=1:
            tree_root.right = self.constructFromPrePost(pre[left_len:],post[left_len:])
            
        return tree_root
已知中序后序遍历构造二叉树
 没有前序遍历时，使用后序遍历定根节点     

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:  
	len_in = len(inorder)
  len_post = len(postorder)
  if len_in==0 or len_in!=len_post:
      return  None
  
  tree_root = TreeNode(postorder[-1])
  postorder = postorder[:-1]
  left_len = 0
  
  for i in inorder:
      if i==tree_root.val:
          break
      else:
          left_len += 1
  
  inorder.remove(tree_root.val)
  if left_len>=1:
      tree_root.left = self.buildTree(inorder[:left_len],postorder[:left_len])
  if len(postorder)-left_len>=1:
      tree_root.right = self.buildTree(inorder[left_len:],postorder[left_len:])
  
  return tree_root

二叉搜索树

​

二叉搜索树的性质:

​ 1.中序遍历的结果有序

​ 2.左子树上的节点都比根节点小，右子树都比根节点大

修剪二叉搜索树

​ 给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def trimBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: TreeNode
        """
        
        if root==None:
            return None
        
        if root.val<L:
            return self.trimBST(root.right,L,R)
        elif root.val>R:
            return self.trimBST(root.left,L,R)
        else:
            root.left = self.trimBST(root.left,L,R)
            root.right = self.trimBST(root.right,L,R)
        
        return root
把二叉搜索树转化为累加树

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

1
2
3
4
5
6
7
8
9
输入: 二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        root_ref = root
        stack = []
        prev = 0
        while stack or root:
            while root:
                stack.append(root)
                root = root.right
            root = stack.pop()
            root.val += prev
            prev = root.val
            root = root.left
        return root_ref
验证搜索二叉树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
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
方法一：用搜索二叉树的性质1，中序遍历一定有序，那么我们只需要在中序遍历中保证后添加的数比前面添加的最后一个数的即可，出现不符合这一规律的直接返回False
	注：这里需要特别注意，二叉搜索数中不能出现两个一样的值，因此不能直接输出中序序列和排序号好的序列对比
def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        stack  = []
        pos = root
        
        result = []
        while stack or pos:
            while pos:
                stack.append(pos)
                pos = pos.left
            
            pos = stack.pop()
            if result!=[]:
                if result[-1]<pos.val:
                    result.append(pos.val)
                else:
                    return False
            else:
                result.append(pos.val)
            pos = pos.right
        
        return True