366. Find Leaves of Binary Tree

Leetcode

https://leetcode.com/problems/find-leaves-of-binary-tree/

題目

Given the root of a binary tree, collect a tree's nodes as if you were doing this:

• Collect all the leaf nodes.

• Remove all the leaf nodes.

• Repeat until the tree is empty.

Example 1:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

Example 2:

Input: root = [1]
Output: [[1]]

解答

• 方法一

一輪一輪的把所有葉子節點挑出來後，再依序加入結果的矩陣

var findLeaves = function(root) {
    let res = [];
    let temp = [];
    
    const postOrder = (node) => {
        if(!node) return true;
        const children = [node.left, node.right];
        
        // 找到葉子節點
        if (children.every(child => !child)) {
            temp.push(node.val);
            return true;
        }
        
        // 如果子節點是葉子節點的話，將其移出 tree
        if (node.left && postOrder(node.left)) {
            node.left = null;
        }
        if (node.right && postOrder(node.right)) {
            node.right = null;
        }
    }
    
    while(root.left || root.right) {
        postOrder(root);
        res.push(temp);
        temp = [];
    }
    // 最後剩 root 節點也需要 push 進矩陣
    res.push([root.val]);
    return res;
};

Runtime: 99 ms, faster than 21.85% of JavaScript online submissions for Find Leaves of Binary Tree.

Memory Usage: 42.4 MB, less than 56.31% of JavaScript online submissions for Find Leaves of Binary Tree.

• 方法二

計算每個節點的高度，依序存到結果矩陣 [ 高度為0的節點, 高度為1的節點, ......]

var findLeaves = function(root) {
    const res = [];
    
    const getHeight = (node) => {
        if(!node) return -1;
        
        const leftHeight = getHeight(node.left);
        const rightHeight = getHeight(node.right);
        
        const selfHeight = Math.max(leftHeight, rightHeight) + 1;
        
        const selfArr = res[selfHeight];
        if (selfArr) {
            selfArr.push(node.val);
        } else {
            res[selfHeight] = [node.val];
        }
        return selfHeight;
    }
    
    getHeight(root);
    return res;
};

Runtime: 90 ms, faster than 35.45% of JavaScript online submissions for Find Leaves of Binary Tree.

Memory Usage: 42.2 MB, less than 67.03% of JavaScript online submissions for Find Leaves of Binary Tree.