我知道如果兩個節點處于同一級別并且具有不同的父節點，則它們是表親，所以這是我的邏輯/演算法。我正在創建兩個布爾方法findLevel和兄弟姐妹（對這兩種方法都使用前序遍歷）。然后我檢查 main 方法printCousins，如果 findLevel 為 true 而不是兄弟，則添加到arrayList. 但是如果有人能告訴我我做錯了什么，我的解決方案就是錯誤的。
static boolean findLevel(Node root, Node find, int level) {
boolean status = false;
if (root == null || find == null)
return false;
if (root == find)
status = true;
findLevel(root.left, find, level 1);
findLevel(root.right, find, level 1);
return status;
}
static boolean sibling(Node root, Node find) {
boolean status = false;
if (root == null || find == null)
return false;
if (root.left == find && root.right == find)
status = true;
sibling(root.left, find);
sibling(root.right, find);
return status;
}
uj5u.com熱心網友回復：
在您的方法中，您似乎假設堂兄弟只能有 1 個不同的父母。我們越深入，特定節點的不同父find節點就越多，或者您可以說堂兄弟越多。此外，if(root.left == find && root.right == find){由于樹中不能有 2 個相同的節點，因此沒有意義，尤其是find.
在您的printCousins中，您需要找到find節點的級別，然后通過將其傳遞給siblings方法來收集它的所有表兄弟。
public static ArrayList<Integer> printCousins(Node root, Node find){
//code here
ArrayList<Integer> arr = new ArrayList<>();
int level = findLevel(root, find, 0);
if(level == -1){
arr.add(-1);
return arr;
}
siblings(root, find, arr, 0, level);
if(arr.isEmpty()){
arr.add(-1);
}
return arr;
}
由于您使用深度優先搜索技術，您可以首先找到find節點的級別，如下所示：
static int findLevel(Node root, Node find, int level){
if(root == null) return -1;
if(root == find) return level;
int level = findLevel(root.left, find, level 1);
if(level == -1) level = findLevel(root.right, find, level 1);// only go to the right side of the node if not found on the left part
return -1;
}
在siblings中，您將添加所有這些節點arr，并level仔細檢查沒有find作為孩子之一的父節點，從而確保不同的父節點具有相同級別的要求。
static void siblings(Node root, Node find, ArrayList<Integer> arr, int curr_level, int level){
if(root == null || curr_level > level || root == find) return;
if(curr_level 1 == level){
if(root.left == find || root.right == find) return; // making sure either of the kids isn't 'find'
}
if(curr_level == level){
arr.add(root.val);
return;
}
siblings(root.left, find, arr, curr_level 1, level);
siblings(root.right, find, arr, curr_level 1, level);
}
uj5u.com熱心網友回復：
我可以在這個任務中看到簡單的BFS - 廣度優先搜索。您所需要做的就是找到一個級別，其中您的目標節點并列印具有不同父節點的同一級別的所有其他節點，如果您保留每個節點的父節點，這可能會非常容易（我提供使用附加類來做到這一點NodeWithParent）。
// This is a class you have to provide a Tree
public static class Node {
private final int value;
private Node left;
private Node right;
public Node(int value) {
this.value = value;
}
}
// This is an internal class to keep the node's parent
private static class NodeWithParent {
private final Node delegate;
private final Integer parent;
public NodeWithParent(Node delegate, Integer parent) {
this.delegate = delegate;
this.parent = parent;
}
}
public static Set<Integer> printCousins(Node root, int find) {
NodeWithParent tmp = new NodeWithParent(root, null);
Deque<NodeWithParent> levelNodes = new LinkedList<>();
levelNodes.add(tmp);
// not null means target node was found at current level
NodeWithParent findNode = root.value == find ? tmp : null;
while (!levelNodes.isEmpty()) {
if (findNode != null)
return getNodesNotForParent(levelNodes, findNode);
int total = levelNodes.size();
for (int i = 0; i < total; i ) {
NodeWithParent node = levelNodes.remove();
NodeWithParent findNode1 = addNotNullChild(node.delegate.left, node.delegate.value, find, levelNodes);
NodeWithParent findNode2 = addNotNullChild(node.delegate.right, node.delegate.value, find, levelNodes);
if (findNode == null)
findNode = findNode1 == null ? findNode2 : findNode1;
}
}
return Set.of();
}
private static NodeWithParent addNotNullChild(Node childNode, int parentValue, int find, Deque<NodeWithParent> levelNodes) {
if (childNode == null)
return null;
NodeWithParent node = new NodeWithParent(childNode, parentValue);
levelNodes.add(node);
return childNode.value == find ? node : null;
}
private static Set<Integer> getNodesNotForParent(Collection<NodeWithParent> nodes, NodeWithParent findNode) {
return nodes.stream()
.filter(node -> !Objects.equals(node.parent, findNode.parent))
.map(node -> node.delegate.value)
.collect(Collectors.toSet());
}
uj5u.com熱心網友回復：
下面提供的二叉樹的實作允許創建與您的示例具有完全相同結構的樹（查看輸出）。
這棵樹是平衡的，根據提供的樹模式，它不是 BST。因此，下面的代碼僅在添加節點時適應平衡，以便整體結構與您的示例相匹配。
代碼使用經典的 BFS 和 DFS 演算法。
public class BinaryTree {
private Node root;
private Map<Integer, Node> idToNode;
private BinaryTree(Node root) {
this.root = root;
this.idToNode = new HashMap<>();
}
public static BinaryTree getInstance(int rootId, int... elements) {
BinaryTree tree = new BinaryTree(new Node(rootId));
tree.addElements(elements);
tree.discoverAllNodes();
return tree;
}
public void addElements(int... elements) {
IntStream.of(elements)
.forEach(root::addElement);
}
public void discoverAllNodes() {
Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
Node cur = stack.pop();
idToNode.put(cur.getId(), cur);
if (cur.getLeft() != null)
stack.push(cur.getLeft());
if (cur.getRight() != null)
stack.push(cur.getRight());
}
}
public List<Node> getCousins(int find) {
Node target = new Node(find);
if (target.equals(root)) return Collections.emptyList();
int targetLevel = getNodeLevel(find);
Queue<Node> curLevelNodes = new ArrayDeque<>();
Queue<Node> nextLevelNodes = new ArrayDeque<>();
curLevelNodes.add(root);
for (int level = 0; level < targetLevel; level ) {
while (!curLevelNodes.isEmpty()) {
Node cur = curLevelNodes.remove();
if (cur.getLeft() != null && !cur.getLeft().equals(target))
nextLevelNodes.add(cur.getLeft());
if (cur.getRight() != null && !cur.getRight().equals(target))
nextLevelNodes.add(cur.getRight());
}
Queue<Node> emptyQueue = curLevelNodes; // reusing empty queue to avoid creating new collection
curLevelNodes = nextLevelNodes;
nextLevelNodes = emptyQueue;
}
return Collections.unmodifiableList(new ArrayList<>(curLevelNodes));
}
public int getNodeLevel(int find) {
Node target = idToNode.get(find);
if (target.equals(root)) return 0;
boolean targetIsFound = false;
int level = 0;
Queue<Node> curLevelNodes = new ArrayDeque<>();
Queue<Node> nextLevelNodes = new ArrayDeque<>();
curLevelNodes.add(root);
for (; !targetIsFound; level ) {
while (!curLevelNodes.isEmpty()) {
Node cur = curLevelNodes.remove();
if (curNodePointToTargetNode(target, cur)) {
targetIsFound = true;
break;
}
if (cur.getLeft() != null && !cur.getLeft().equals(target))
nextLevelNodes.add(cur.getLeft());
if (cur.getRight() != null && !cur.getRight().equals(target))
nextLevelNodes.add(cur.getRight());
}
if (targetIsFound) continue;
Queue<Node> emptyQueue = curLevelNodes; // reusing empty queue to avoid creating new collection
curLevelNodes = nextLevelNodes;
nextLevelNodes = emptyQueue;
}
return level;
}
private boolean curNodePointToTargetNode(Node target, Node cur) {
return cur.getLeft() != null && cur.getLeft().equals(target) ||
cur.getRight() != null && cur.getRight().equals(target);
}
public Node getRoot() {
return root;
}
public Map<Integer, Node> getIdToNode() {
return Collections.unmodifiableMap(idToNode);
}
public static class Node {
private final int id;
private Node left;
private Node right;
public Node(int id) {
this.id = id;
}
public void addElement(int nextId) {
if (left == null) {
left = new Node(nextId);
return;
}
if (right == null) {
right = new Node(nextId);
return;
}
if (left.getMinHeight() <= right.getMinHeight()) {
left.addElement(nextId);
}
else {
right.addElement(nextId);
}
}
private int getMinHeight() {
if (left == null || right == null) return 0;
int height = 0;
boolean leafNodeFound = false;
Queue<Node> curLevelNodes = new LinkedList<>();
Queue<Node> nextLevelNodes = new LinkedList<>();
curLevelNodes.add(this);
for (; !leafNodeFound; height ) {
while (!curLevelNodes.isEmpty()) {
Node cur = curLevelNodes.remove();
if (cur.getLeft() == null || cur.getRight() == null) {
leafNodeFound = true;
break;
}
nextLevelNodes.add(cur.getLeft());
nextLevelNodes.add(cur.getRight());
}
Queue<Node> emptyQueue = curLevelNodes; // reusing empty queue to avoid creating new collection
curLevelNodes = nextLevelNodes;
nextLevelNodes = emptyQueue;
}
return height;
}
public int getId() {
return id;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return id == node.id;
}
@Override
public int hashCode() {
return Objects.hash(id);
}
@Override
public String toString() {
return "Node{" id '}';
}
}
}
主要的
public static void main(String[] args) {
BinaryTree tree = BinaryTree.getInstance(1, 2, 3, 4, 5, 6, 7);
System.out.println("Root: " tree.getRoot());
System.out.println("All nodes: " tree.getIdToNode());
System.out.println("Node 2 - level: " tree.getNodeLevel(2));
System.out.println("Node 2 - cousins: " tree.getCousins(2));
System.out.println("Node 3 - level: " tree.getNodeLevel(3));
System.out.println("Node 3 - cousins: " tree.getCousins(3));
System.out.println("Node 4 - level: " tree.getNodeLevel(4));
System.out.println("Node 4 - cousins: " tree.getCousins(4));
System.out.println("Node 5 - level: " tree.getNodeLevel(5));
System.out.println("Node 5 - cousins: " tree.getCousins(5));
System.out.println("Node 6 - level: " tree.getNodeLevel(6));
System.out.println("Node 6 - cousins: " tree.getCousins(6));
System.out.println("Node 7 - level: " tree.getNodeLevel(7));
System.out.println("Node 7 - cousins: " tree.getCousins(7));
}
輸出
Root: Node{1}
All nodes: {1=Node{1}, 2=Node{2}, 3=Node{3}, 4=Node{4}, 5=Node{5}, 6=Node{6}, 7=Node{7}}
Node 2 - level: 1
Node 2 - cousins: [Node{3}]
Node 3 - level: 1
Node 3 - cousins: [Node{2}]
Node 4 - level: 2
Node 4 - cousins: [Node{5}, Node{6}, Node{7}]
Node 5 - level: 2
Node 5 - cousins: [Node{4}, Node{6}, Node{7}]
Node 6 - level: 2
Node 6 - cousins: [Node{4}, Node{5}, Node{7}]
Node 7 - level: 2
Node 7 - cousins: [Node{4}, Node{5}, Node{6}]
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/420158.html
標籤：