剑指Offer之二叉树系列：从上往下打印二叉树(I、II、III)、二叉树中和为某一值的路径

Hasana ·

更新时间:2024-09-21

· 635 次阅读

剑指Offer（二十二）：从上往下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:

给定二叉树: [3,9,20,null,null,15,7],

[3,9,20,15,7]

解题思路：先进先出，队列的思想

从上到下打印二叉树的规律：每一次打印一个结点的时候，如果该结点有子结点，则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直至队列中所有的结点都打印出来为止。

代码实现 C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector levelOrder(TreeNode* root) {
        TreeNode* fr;
        vector result;
        queue que;
        if(root == NULL){
            return result;
        }
        que.push(root);
        while(!que.empty()){
            fr = que.front(); 
            result.push_back(fr->val);
            if(fr->left!=NULL){
                que.push(fr->left);
            }
            if(fr->right!=NULL){
                que.push(fr->right);
            }
            que.pop();
        }
        return result;
    }
};

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        result = []
        tmp = [root]
        while len(tmp):
            cur = tmp.pop(0)
            result.append(cur.val)
            if cur.left:
                tmp.append(cur.left)
            if cur.right:
                tmp.append(cur.right)
        return result

剑指Offer（六十）：把二叉树打印成多行

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:

给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
[3],
[9,20],
[15,7]
]

解题思路和上题一样，利用队列的思想：

按层打印：题目要求的二叉树的从上至下打印（即按层打印），又称为二叉树的广度优先搜索（BFS）。BFS 通常借助队列的先入先出特性来实现。

每层打印到一行：将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。

算法流程：

特例处理：当根节点为空，则返回空列表 [] ；初始化：打印结果列表 res = [] ，包含根节点的队列 queue = [root] ； BFS 循环：当队列 queue 为空时跳出；新建一个临时列表 tmp ，用于存储当前层打印结果；当前层打印循环：循环次数为当前层节点数（即队列 queue 长度）；出队：队首元素出队，记为 node；打印：将 node.val 添加至 tmp 尾部；添加子节点：若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；将当前层结果 tmp 添加入 res 。返回值：返回打印结果列表 res 即可。

注意：Python 中使用 collections 中的双端队列 deque() ，其 popleft() 方法可达到 O(1)时间复杂度；列表 list 的 pop(0) 方法时间复杂度为 O(N) 。

Python代码实现：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res, queue = [], collections.deque()
        queue.append(root)
        while queue:
            tmp = []
            for _ in range(len(queue)):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(tmp)
        return res

剑指Offer（五十九）：按之字顺序打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

解题思路：层序遍历 + 双端队列（奇偶层逻辑分离）

算法流程：

特例处理：当树的根节点为空，则直接返回空列表 [] ；初始化：打印结果空列表 res ，包含根节点的双端队列 deque ； BFS 循环：循环打印奇 / 偶数层，当 deque 为空时跳出；打印奇数层：从左向右打印，先左后右加入下层节点；若 deque 为空，说明向下无偶数层，则跳出；打印偶数层：从右向左打印，先右后左加入下层节点；将当前层结果 tmp 转化为 list 并添加入 res ；返回值：返回打印结果列表 res 即可； 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res, deque = [], collections.deque()
        deque.append(root)
        while deque:
            tmp = []
            # 打印奇数层
            for _ in range(len(deque)):
                # 从左向右打印
                node = deque.popleft()
                tmp.append(node.val)
                # 先左后右加入下层节点
                if node.left: deque.append(node.left)
                if node.right: deque.append(node.right)
            res.append(tmp)
            if not deque: break # 若为空则提前跳出
            # 打印偶数层
            tmp = []
            for _ in range(len(deque)):
                # 从右向左打印
                node = deque.pop()
                tmp.append(node.val)
                # 先右后左加入下层节点
                if node.right: deque.appendleft(node.right)
                if node.left: deque.appendleft(node.left)
            res.append(tmp)
        return res

剑指Offer（二十四）：二叉树中和为某一值的路径

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

示例:
给定如下二叉树，以及目标和 sum = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

[
[5,4,11,2],
[5,8,4,5]
]

解题思路–深度优先搜索 深度优先搜索。使用前序遍历，使用两个全局变量result和tmp，result来存放最终结果，tmp用来存放临时结果。每次遍历，我们先把root的值压入tmp，然后判断当前root是否同时满足：与给定数值相减为0；左子树为空；右子树为空。如果满足条件，就将tmp压入result中，否则，依次遍历左右子树。需要注意的是，遍历左右子树的时候，全局变量tmp是不清空的，直到到了根结点才请空tmp。 代码实践： C++实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector> pathSum(TreeNode* root, int sum) {
        if(root == NULL){
            return result;
        }
        tmp.push_back(root->val);
        if((sum- root->val ) == 0 && root->left == NULL && root->right == NULL){
            result.push_back(tmp);
        }
        //遍历左子树
        pathSum(root->left, sum - root->val);
        //遍历右子树
        pathSum(root->right, sum - root->val);
        tmp.pop_back();
        return result;
    }
private:
    vector<vector> result;
    vector tmp;
};

Python实现:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        if not root:
            return []
        if not root.left and not root.right and sum == root.val:
            return [[root.val]]
        res = []
        left = self.pathSum(root.left, sum-root.val)
        right = self.pathSum(root.right, sum-root.val)
        for i in left+right:
            res.append([root.val]+i)
        return res