二叉树

发表于 | 分类于 | | 阅读数 次
字数统计: 1.2k | 阅读时长 ≈ 4

老常见了，做就是了，但是比较有意思的看到有人提到，其实很多算法题目都是二叉树的变种，可以先刷二叉树，构建框架思维，觉得还挺有意思的，认真研读刷一下，题目都来自leetcode

Tips：

wait

遍历

递归

递归的就不说了，中心思想就是整棵树和每一颗子树的操作是一样的，所以输出当前节点后，依次遍历相应的子树

1
2
3
4
def preorder(root):
    print(root.val)
    preorder(root.left)
    preorder(root.right)

迭代

前序：

前序相对简单一些，思路上来讲，我们需要先输出根节点，然后输出左、右子树，但是如果左子树还有子树，那就需要接着往下输出，接着再返回来输出右子树，所以需要记录右子树，流程上就是：输出根节点，输出左儿子，输出左儿子的子树，输出右儿子的子树，那如何保留子树呢？可以借助到栈，我们先压入根节点，然后出栈、输出，接着把其儿子压入栈，然后儿子出栈、输出，再压入其儿子，而需要注意栈是先进后出，所以儿子入栈时，需要先入右儿子、再入左儿子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        stack.append(root)
        result = []
        while stack:
            out = stack.pop()
            if out:
                result.append(out.val)
                if out.right != None:
                    stack.append(out.right)
                if out.left != None:
                    stack.append(out.left)
        return result
中序：

中序遍历，也是利用栈，然后按照左、中、右输出，也就是，首先需要找树最左最底的子树输出，然后再往上回溯，再看该节点的右子树，所以流程就是：先把指针指向头，然后开始找最左最底子树，找的过程中一路压栈，找到后，开始出栈、输出，然后看他是否有右子树，

这里有个纠结过的点是，怎么不管根节点呢？最左输出完就管右了？其实因为每一个根节点其实就是上一颗的左子树，所以输出完这个最左最底子树A后，其实是已经遍历完他的左儿子（None）了，所以输出A，然后输出A的right，往上，A的父亲已经输出完A这个左儿子了，所以自己输出完，转向右儿子就可以了

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

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        cur = root
        result = []
        while stack or cur:
            #找到最左最底子树
            while cur:
                stack.append(cur)
                cur = cur.left
            #输出最左最底子树
            out = stack.pop()
            result.append(out.val)
            #如果有右子树，指针转向右子树输出
            if out.right:
                cur = out.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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        stack_out = []
        # 根节点入栈
        stack_stored = [root]
        # 先全部按中、左、右入栈1
        while stack_stored:
            out = stack_stored.pop()
            # 出栈1，入栈2
            if out:
                stack_out.append(out.val)
                if out.left:
                    stack_stored.append(out.left)
                if out.right:
                    stack_stored.append(out.right)
        return stack_out[::-1]
层次：

层次遍历，从上到下，从左到右，依次出去，那就要用到先进先出的队列了，从上到下，从左到右，依次入列，出列后即将其子树入列，直至所有出列完毕

226.翻转二叉树

这个其实就直接翻就好了，左子树递归，右子树递归，俩儿子交换

114.二叉树展开链表

看到示例其实就是前序遍历的展开，可以通过前序遍历得到相应的List，但是该问题要求不能return别的，需要原地替换，所以还需要把List里的数据再插回原来的root，需要注意的是，不要太死板在List里插入value，事实上，可以直接append node，这样回头插入的时候，就可以直接left or right = datas[i]， 很方便

官方题解：二叉树展开为链表

递归：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        datas = []
        def preorder(root):
            if root:
                datas.append( root )
                preorder(root.left) 
                preorder(root.right) 
        
        preorder(root)
        lenofdatas = len(datas)
        for i in range(1,lenofdatas):
            prev, curr = datas[i - 1], datas[i]
            prev.left = None
            prev.right = curr
        return root

迭代：

参考Blog：

学习算法和刷题的框架思维

手把手带你刷二叉树（第一期）

0%