c++,求二叉树从根结点到其中一个叶子的最短路径

如果node有父节点指针的话还是比较容易的

c++11可以通过,低版本可能node的new那里要改一下

#include 
#include 
#include 
using namespace std;

struct node
{
  node *parent,*left,*right;
  char key;
};

string shortestPath(node* root)
{
  // 广度优先搜索
  queue nqueue;
  nqueue.push(root);
  node *pnode;
  while (!nqueue.empty())
    {
      pnode = nqueue.front();
      nqueue.pop();
      if (pnode->left == NULL && pnode->right == NULL)
	break;
      if (pnode->left)
	nqueue.push(pnode->left);
      if (pnode->right)
	nqueue.push(pnode->right);
    }
  // pnode是同一深度第一个没有孩子的节点即叶节点
  string s;
  while (pnode != root)//回溯
    {
      s = pnode->key + s;
      pnode = pnode->parent;
    }
  s = root->key +s;
  return s;
}

int main()
{
  node *A = new node{0,0,0,'A'},*B = new node{0,0,0,'B'},*C = new node{0,0,0,'C'},*D = new node{0,0,0,'D'};
  A->left = B,B->parent = A;
  A->right = C,C->parent = A;
  B->left = D,D->parent = B;
  cout << shortestPath(A) << endl;
  A->right = NULL;
  B->left = C,C->parent = B;
  cout << shortestPath(A) << endl;
}