Tree and Divide Conquer

Posted on

Tree and Divide Conquer

最近做二叉树相关的题，被递归搞的晕头转向。

[TOC]

一、树的性质

参考：Tree总结

由于树的结构，这种数据结构很适合用分治（Divide Conquer）

Divide and Conquer模版

递归算法模版；

1
2
3
4
5
6
7
8
9
10
11
12
def traversal(root):
	# base case(none or leaf)
	if not root:
		# do sth
	
	# divide
	left = traversal(root.left)
	right = traversal(root.right)
	
	# Conquer
	res = # merge 
	return res

114 Flatten Binary Tree to Linked List

以 leetcode #114题为例

1)从最简单的case开始

simplest case，树只有一个元素1，直接返回；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# simplest case：
    1
# 两个元素：
    1
   / 
  2   
  ########   
    1
     \
      2
# 三个元素：
    1
   / \
  2   3
# N 个元素
     1
   /   \
LTree  RTree
例子：
    1
   / \
  2   5
 / \   \
3   4   6

当有两个元素时：

1
2
3
4
5
6
def flatten2(root):
    left = root.left
    right = root.right
    if left:
        root.right = left
        root.left = None

当有三个元素时：

1
2
3
4
5
6
7
8
9
10
def flatten3(root):
    # divide 
    left = root.left
    right = root.right
    # merge
    if left:
        root.right = left
        root.left = None
    if right:
        left.right = right

2）一般case

可以将其分为 左子树和右子树，（假设左右都为三个元素（base case），我们可以用上面的程序处理好）。假设左右子树都已经处理完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def flatten(root):
	# base case(none)
    if not root:
        return
    # leaf node
    if not root.left and not root.right:
        return root
    # divide
   	left = root.left
    right = root.right
    # conquer 处理左右子树
    flatten(left)
    flatten(right)
    # merge
    if left:
        root.right=left
        root.left = None
    if right:
        ...

3) merge

如何把子问题的解merge原问题的解？

把子问题的解 merge成问题的解时需要解决一个问题，即如何将右子树链接到左子树的后面？

  1. 左子树的哪个节点去链接右子树根节点？
  2. 如何确定这个节点的位置

根据题意知道，最终生成 linked list 顺序是先序遍历的顺序，故将左子树最右边的叶子节点链接到右子树的根节点；使用python中的全局变量指向当前根节点下的最右叶子节点。

算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
prev = None
def func(root):
	if root is leaf:
		# prev 指向左子树的最右子节点
		prev=root
   left = root.left
   right = root.right
   # 递归处理左子树
   func(left)
   # 如果左子树存在
   if left:
   	# 将root的右子节点指向左子树
   	root.right = left
   	root.left = None
   	# 将左子树最右边的叶子节点指向右子树
   	prev.right = right
   # 递归处理右子树
   func(right)

最终AC的代码：

Python3代码：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.prev = None
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        # base case
        if not root:
            return
        if not root.left and not root.right:
            self.prev=root
            return
       	# divide
        left = root.left
        right = root.right
        # conquer
        self.flatten(left)
        # merge
        if left:
            root.right, root.left = left, None
            self.prev.right = right
        # conquer
        self.flatten(right)

代码精简版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.prev = None
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return
        self.prev = root
        right = root.right
        self.flatten(root.left)
        root.right, root.left=root.left, None
        self.prev.right = right
        self.flatten(right)

从以上代码可以看出，其实就是对 Tree 进行先序遍历,同时将全局变量用作指针

这道题还有其他思路,（修改版的后序遍历）遍历顺序是右子树->左子树->根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.prev = None
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return None
        self.flatten(root.right)
        self.flatten(root.left)

        root.right = self.prev
        root.left = None
        self.prev = root

总结

  1. 对树进行divide conquer ，要把所有的最简单case列出来分析
  2. 将树分为子问题一般比较容易，关键如何将子问题的解merge成原问题的解！
  3. python的全局变量的使用。