366. Find-Leaves-of-Binary-Tree.md

Description

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:

Input: [1,2,3,4,5]

          1
         / \
        2   3
       / \
      4   5

Output: [[4,5,3],[2],[1]]

Explanation:

1. Removing the leaves [4,5,3] would result in this tree:

          1
         /
        2

1. Now removing the leaf [2] would result in this tree:

          1

1. Now removing the leaf [1] would result in the empty tree:

          []

---

python solution

思路很简单，一层一层的提取叶子节点，直到树只剩下一个根节点。

• 如何提取叶子节点？叶子节点的判断：如果一个节点的左子树和右子树都为None，那么它就是叶子节点。
• 如何把叶子节点去掉？在遍历树的过程中，要额外记录当前节点的父节点 和 当前节点是父节点的左节点还是右节点。如果一个节点是叶子节点，把父节点对应的左/右子树设置为None。
• 我们要写一个循环，一层一层的提取。循环的终止条件是什么？当只剩下一个根节点时，说明已经遍历完成。我们做一个全局变量onlyOneNode，用来代表只剩下根节点。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    def __init__(self):
        self.onlyOneNode=False
    def findLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """


		# 一轮遍历，将所有叶子节点找出来放到leaves数组，并将这些叶子节点剪掉
        def findLeavesAndRemove(node, leaves, root, left):  # root表示node的父节点
            if not node: return
            if not node.left and not node.right:
                leaves.append(node.val)
                if root:  # 说明当前树没有遇到终止条件(只剩下根节点)
                    if left:
                        root.left = None
                    else:
                        root.right = None
                else:  # 这个时候只剩下root一个节点。
                    self.onlyOneNode = True
            if node and node.left:
                findLeavesAndRemove(node.left, leaves, node, True)
            if node and node.right:
                findLeavesAndRemove(node.right, leaves, node, False)

        if not root:return []
        res = []
        while not self.onlyOneNode:
            leaves = []
            findLeavesAndRemove(root, leaves, None, None)
            res.append(leaves)
        return res