讨论/《广度优先搜索》 - 练习:二叉树的层次遍历 II/
《广度优先搜索》 - 练习:二叉树的层次遍历 II
共 6 个回复
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i=0;i<size;i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            result.add(new ArrayList<>(list));
        }

        Collections.reverse(result);
        return result;
    }
}

来个Golang的

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    q := new(Queue)
    q.EnQueue(root)
    ans := make([][]int, 0)
    for q.Size() > 0 {
        row := make([]int, 0)
        n := q.Size()
        for i := 0; i < n; i++ {
            node := q.DeQueue()
            row = append(row, node.Val)
            if node.Left != nil {
                q.EnQueue(node.Left)
            }
            if node.Right != nil {
                q.EnQueue(node.Right)
            }
        }
        // ans = append([][]int{row}, ans...) // 这样不用reverse
        ans = append(ans, row)
    }
    reverse(ans)
    return ans
}

func reverse(arr [][]int) {
    left, right := 0, len(arr)-1
    for left < right {
        arr[left], arr[right] = arr[right], arr[left]
        left++
        right--
    }
}

type Queue struct {
    queue []*TreeNode
}

func (q Queue)Size() int {
    return len(q.queue)
}

func (q *Queue)EnQueue(node *TreeNode) {
    if q.queue == nil {
        q.queue = make([]*TreeNode, 0)
    }
    q.queue = append(q.queue, node)
}

func (q *Queue)DeQueue() *TreeNode {
    if q.Size() == 0 {
        return nil
    }
    node := q.queue[0]
    q.queue = q.queue[1:]
    return node
}

c++ 正序 + swap(reverse)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void reverseOp(vector<vector<int>>& ret) {
        int i = 0, j = ret.size() - 1;
        vector<int> temp;
        while(i <= j) {
            temp = ret[i];
            ret[i] = ret[j];
            ret[j] = temp;
            i++;
            j--;
        }
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        //层序遍历
        if(root == nullptr) return {};
        vector<vector<int>> ret;
        vector<int> temp;
        queue<TreeNode*> Q;
        Q.push(root);
        while(!Q.empty()) {
            int curSize = Q.size();
            temp.clear();
            for(int i = 0; i < curSize; i++) {
                TreeNode* node = Q.front();
                temp.push_back(node->val);
                if(node->left != nullptr) Q.push(node->left);
                if(node->right != nullptr) Q.push(node->right);
                Q.pop();
            }
            ret.push_back(temp);
        }
        reverseOp(ret);
        return ret;
    }
};

是的~

这是正序遍历,还少一个reverse

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        q = collections.deque([root])
        res = []
        while q :
            l = []
            for i in range(len(q)) :
                t = q.popleft()
                l.append(t.val)
                if t.left : q.append(t.left)
                if t.right : q.append(t.right)
            res.append(l)
        return res