列印二叉樹每一層除了最右節點的所有節點

---

在這個問題中，我們將列印二叉樹中除了每一層最右節點之外的所有節點。

我們將使用層序遍歷來遍歷二叉樹，並且我們不會列印每一層的最後一個節點，也就是最右節點。

問題陳述 − 我們給定一個包含不同節點的二叉樹。我們需要列印二叉樹中除了最右節點之外的所有節點。

示例

輸入 

          7
       /     \
      8       9
    /   \       \
   2     7       21
        /  \
       21    43

輸出

8
2  7
21

解釋：我們列印了每一層除了最右節點之外的所有節點。

輸入

             35
           /    \    
         74     21    
        /  \    / \       
      32    15 90  576        
     /  \
    45  83

輸出 

74
32 15 90
45

解釋 −在這裡，我們列印除了最右節點之外的所有節點。

方法一

在這種方法中，我們將使用佇列對給定的二叉樹執行層序遍歷。在層序遍歷中，我們不會列印每一層的最後一個節點，以排除每一層的最右節點。

演算法

步驟 1− 為二叉樹節點建立一個 TreeNode 結構。樹節點包含用於儲存資料的 ‘val’ 以及用於跟蹤特定節點的左孩子和右孩子節點的 ‘left’ 和 ‘right’ 指標。

步驟 2 − 之後，定義 createNode() 函式來建立一個新節點。

步驟 2.1 − 建立一個新的 ‘tmp’ 節點，並使用給定的值初始化其值。同時，將左指標和右指標初始化為 NULL。

步驟 2.2 − 從函式返回 ‘tmp’ 節點。

步驟 3 − 在 main() 方法中，透過新增節點來建立一個二叉樹。

步驟 4 − 執行 printNodes() 函式以列印二叉樹的每個節點，除了二叉樹的最右節點。

步驟 5 − 在 printNodes() 函式中，如果頭指標為 NULL，則執行 return 語句。

步驟 6 − 定義佇列來儲存樹節點並插入頭節點。

步驟 7 − 使用 while 迴圈進行迭代。在 while 迴圈中，將佇列大小儲存在 ‘totalNodes’ 變數中。

步驟 8 − 如果 ‘totalNodes’ 為 0，則中斷迴圈。

步驟 9 − 使用巢狀 while 迴圈遍歷每一層。

步驟 10 − 從佇列中彈出第一個元素，如果 ‘totalNodes’ 不等於 1，則列印它。

步驟 11 − 如果當前節點的左孩子存在，則將其推入佇列。

步驟 12 − 如果當前節點的右節點存在，則將其推入佇列。

步驟 13 − 將 ‘totalNodes’ 減 1。

示例

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val;
    struct TreeNode *left, *right;
};
TreeNode *createNewNode(int val) {
    TreeNode *tmp = new TreeNode;
    tmp->val = val;
    tmp->left = NULL;
    tmp->right = NULL;
    return (tmp);
}
void printNodes(TreeNode *head) {
    if (head == NULL)
        return;
    queue<TreeNode *> que;
    que.push(head);
    while (true) {
        int totalNodes = que.size();
        if (totalNodes == 0)
            break;
        while (totalNodes > 0) {
            TreeNode *node = que.front();
            // If node is not rightmost print
            if (totalNodes != 1)
                cout << node->val << " ";
            que.pop();
            // Insert the left and right node of the current node in the queue
            if (node->left != NULL)
                que.push(node->left);
            if (node->right != NULL)
                que.push(node->right);
            totalNodes--;
        }
        cout << "\n";
    }
}
int main() {
    TreeNode *head = createNewNode(35);
    head->left = createNewNode(74);
    head->right = createNewNode(21); 
    head->right->left = createNewNode(90);
    head->right->right = createNewNode(576);
    head->left->left = createNewNode(32);
    head->left->right = createNewNode(15);
    head->left->left->left = createNewNode(45);
    head->left->right->right = createNewNode(83);
    printNodes(head);
    return 0;
}

輸出

74 
32 15 90 
45

時間複雜度 − O(N)，其中 N 是二叉樹中節點的總數。

空間複雜度 − O(M)，其中 M 是一個層級中節點的最大數量。

我們學習瞭如何使用層序遍歷來列印除了最右節點之外的每個二叉樹節點。但是，程式設計師可以編寫程式碼來列印除了最左節點之外的每個二叉樹節點。在這種情況下，程式設計師需要列印佇列中除了第一個節點之外的所有節點。