Druck-Blatt-Knoten in einen binären Baum von rechts nach Links?

Führen Sie eine Tiefe-ersten traversal des Baums, den Umgang mit den rechten sub-Bäume erste und drucken nur die Blattknoten.

Der einfachste Weg, um dies zu implementieren, ist mit einer rekursiven Funktion.

void printLeafNodes(BinaryTreeNode* treePtr) {
  if(treePtr.leftChild == null && treePtr.rightChild == null) {
    //This is a leaf node; print its value
  } else {
    //Recurse on right subtree
    if(treePtr.rightChild != null) {
      printLeafNodes(treePtr.rightChild);
    }
    //Recurse on left subtree
    if(treePtr.leftChild != null) {
      printLeafNodes(treePtr.leftChild);
    }
  }
}

Diese Seite ist sehr hilfreich für die Visualisierung der Lösung: Baum Traversal.

Würden Sie brauchen, um eine rekursive Methode, beginnen, wobei die Methode der top-level-Knoten eines binären Baums.

In der pseudocode, gehe ich davon aus, dass jeder Knoten ist definiert mit "rechts" und "Links" - Mitglieder, die selbst Knoten und eine Eigenschaft "name", um etwas zu drucken über den Knoten. Die Methode könnte wie folgt Aussehen, in keiner Sprache, da Sie sagte pseudocode:

function processNode(parent) {
    if(parent.right = null AND parent.left = null)
        print parent.name
    if(parent.right <> null)
        processNode(parent.right)
    if(parent.left <> null)
        processNode(parent.left)
}

Dann Sie würde beginnen mit:

processNode(topNode)

Drucken Blatt-Knoten, während Sie die level-order-Traversierung in umgekehrter Reihenfolge mit Ausnahme der Knoten, die nicht Blatt.

Vermutlich wissen Sie das traversieren eines binären Baums, um mit Rekursion.

void visit(Node node) {
     if(node.hasLeft()) {
         visit(node.getLeft());
     }
     handleValue(node.value); //print or whatever
     if(node.hasRight()) {
         visit(node.getRight());
     }
}

Werden Sie feststellen, dass, wenn Sie dies tun, Sie sind bereits mit der Handhabung der Blätter in Links-nach-rechts Reihenfolge, in der neben der Verarbeitung von nicht-Blatt-Knoten.

Besuchen von rechts nach Links, nur in umgekehrter Reihenfolge der Anweisungen -- so besuchen Sie die rechts, dann Bearbeiten Sie den Wert, dann besuchen Sie die Links.

Drucken nur Blattknoten, Sie müssen nur eine if - Anweisung um handleValue, sagt er zu nur ausgegeben, wenn der Knoten ein Blatt ist. Ein Knoten ist ein Blatt, wenn es weder einen linken noch rechten Kind-Knoten.

Ich weiß, dass ich bin, er ein Alter thread, aber ich denke, es kann helfen, andere Leser dieses Threads. Wenn Sie sprechen über die interview-Frage, denke ich, dass die rekursive Antwort ist nur ein kleiner Teil der Antworten, und der interviewer zu hören, wie der iterative Ansatz. Der rechts in Links-traversal (Druck) ist keine reguläre Prä - /post - /inorder traversalen, die beschrieben ist im wiki. Der main Idee ist hier, dass Sie brauchen, um Recht zu gehen, so lange wie Sie können und starten Sie den Druck aus der rechten Knotens zuerst, dann seine Eltern und erst dann den linken Teilbaum.

Rekursiv:

printRightToLeft(Node root){
  if (root == null)
     return;

  //You can check root.right and root.left for null before calling the
  //printRightToLeft function to avoid pushing unneeded data to recursion
  //call stack.

  printRightToLeft(root.right);
  if (root.right == null && root.left == null)
     print(root);
  printRightToLeft(root.left);
}

Iterativ:

printRightToLeft(Node root){
  if (root == null)
    return;

  Stack s = new Stack();
  s.push(root);

  while(!s.isEmpty()){
    Node n = s.top();

    if (n.right != null && !n.visited){
      s.push(n.right);
      n.visited = true;
    } else {
      s.pop();

      if (n.right == null && n.left == null)
         print(n);

      if (n.left != null)
         s.push(n.left);
    }
}