二叉树Zigzag Level Order Traversal的算法的时间复杂度如何？ [英] What's tight time complexity of this algorithm for Binary Tree Zigzag Level Order Traversal?

问题描述

二叉树Z字形水平顺序遍历
给定一个二叉树，返回Zigzag水平顺序遍历其节点的值。
（即从左到右，然后从右到左，用于下一级别
，并在之间切换）。

Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (i.e.from left to right, then right to left for the next level andalternate between).

strong>给定二叉树{3,9,20，＃，＃，15,7}，

For example: Given binary tree {3,9,20,#,#,15,7},

        3 
       / \ 
      9   20 
     / \ 
   15   7 

返回的Zigzag级别顺序遍历为：

return its zigzag level order traversal as:

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

---

我个人认为，
时间复杂度 = O（n * height），n是节点数，height是

---

Personally I think,
time complexity = O(n * height), n is the number of nodes, height is the height of the given binary tree.

   getHeight()             => O(n) 
   traverseSpecificLevel() => O(n)
   reverseVector()         => O(n)
   swap()                  => O(1)

---

C ++ $ b

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int>> list;

        // Input validation.
        if (root == NULL) return list;

        // Get the height of the binary tree.
        int height = getHeight(root);

        bool left_to_right = true;
        for (int level = 0; level <= height; level ++) {
            vector<int> subList;
            traverseSpecificLevel(root, level, subList);

            if (left_to_right == true) {
                // Add subList into list.
                list.push_back(subList);
                // Update left_to_right flag.
                left_to_right = false;

            } else {
                // Reverse subList.
                reverseVector(subList);
                // Add reversed subList into list.
                list.push_back(subList);
                // Update left_to_right flag.
                left_to_right = true;
            }
        }
        return list;
    }

    int getHeight(TreeNode *root) {
        // Base case.
        if (root == NULL || (root->left == NULL && root->right == NULL)) return 0;
        else return 1 + max(getHeight(root->left), getHeight(root->right));
    }

    void traverseSpecificLevel(TreeNode *root, int level, vector<int> &subList) {
        // Base case.
        if (root == NULL) return;
        if (level == 0) {
            subList.push_back(root->val);
            return;
        }

        // Do recursion.
        traverseSpecificLevel(root->left, level - 1, subList);
        traverseSpecificLevel(root->right, level - 1, subList);
    }

    void reverseVector(vector<int> &list) {
        // Input validation.
        if (list.size() <= 1) return;

        int start = 0;
        int end = list.size() - 1;
        while (start < end) {
            swap(list, start, end);

            start ++;
            end --;
        }
    }

    void swap(vector<int> &list, int first, int second) {
        int tmp = list[first];
        list[first] = list[second];
        list[second] = tmp;
    }
};

推荐答案

创建一个大小为max_height的向量>结果。遍历树递归地维护节点的级别。对于每个节点将其值推回到结果[level]。比起只是反向结果[1]，结果[3]，...。

You can do it in linear time. Create a vector > result with size max_height. Traverse a tree recursively maintaining a level of a node. For every node push back its value to a result[level]. Than just reverse result[1], result[3], ... .

顺便说一句，有一个 swap ）函数和 reverse（a.begin（），a.end（））函数（其中 a 是一个向量），你可以使用它们，而不是自己实现它们。包括算法。

By the way, there is a swap(x,y) function and reverse(a.begin(), a.end()) function (where a is a vector), you may use them instead of implementing them by yourself. Include algorithm for it.

这篇关于二叉树Zigzag Level Order Traversal的算法的时间复杂度如何？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！