Binary Tree Level Order Traversa

2016-10-31  本文已影响63人  郑明明

这个算法和另外一篇文章的区别在于这个算法要求的是从下往上进行遍历,两种算法的唯一不同点在于数组的存入顺序
改动点:递归的方式仍然保持不变,但是将先递归到的存入到数组的最后一个,然后依次往前存,由于递归的顺序是从上往下,存入的顺序是从下往上,就可以实现这种遍历模式

vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> allResult(getMaxDeepth(root));
        soluteForLevelOrder(allResult, root, getMaxDeepth(root) - 1);
        return allResult;
    }
    // 返回最大深度
    int getMaxDeepth (TreeNode *treeNode) {
        TreeNode *tempTreeNode = treeNode;
        if (tempTreeNode == NULL) {
            return 0;
        }
        int left = getMaxDeepth(tempTreeNode->left);
        int right = getMaxDeepth(tempTreeNode->right);
        return (left > right ? left : right) + 1;
    }

    // 获取处理结果
    void soluteForLevelOrder (vector<vector<int>> &vector, TreeNode *treeNode, int level) {
        if (treeNode == NULL) {
            return;
        }
        vector[level].push_back(treeNode->val);
        soluteForLevelOrder(vector, treeNode->left, level-1);
        soluteForLevelOrder(vector, treeNode->right, level-1);
    }
上一篇 下一篇

猜你喜欢

热点阅读