二叉树问题 - 确定最长路径

Question

确定节点不相连的最长集合？网上有类似的例子吗？

      1
     / \
    2   3
   / \   \
  4   5   6
         / \
        7   8

Examples of Sets:
1,4,5,6 = 4
2,6 = 2
1,4,5,7,8 = 5
3,4,5,7,8 = 5

Answer = 5

Answer 1

您可以按如下方式最大化集合：

收集每个叶节点，然后在树中向上工作，并在收集到它的近一个子节点时收集一个节点。

您可以使用深度优先、post 顺序、递归算法来实现。

这是 JavaScript 中的一个实现，它创建示例树然后在其上运行算法：

// Standard Node class for a binary tree
class Node {
    constructor(value, left=null, right=null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

// Main algorithm
function getNodes(root) {
    let set = [];
    
    // Recursive function that returns 1 when the
    //    given node has been collected, 0 otherwise.
    function recur(node) {
        if (node != null && recur(node.left) + recur(node.right) == 0) {
            set.push(node.value);
            return 1;
        }
        return 0;
    }
    // Traverse the tree in post order fashion
    recur(root);
    
    return set;
}

// Build he example tree
let root = new Node(1,
    new Node(2,
        new Node(4), new Node(5)
    ),
    new Node(3,
        null,
        new Node(6,
            new Node(7), new Node(8)
        )
    )
);

// Run the algorithm
let result = getNodes(root);

// Outout the result
console.log(result);

二叉树问题 - 确定最长路径

Binary Tree Question - determine the longest path

tree

binary-tree