回溯法和树的先序遍历

 

先序遍历树,记录全部从根节点到叶子结点的路径。递归

void preOrder(Node* root, vector<int>& path) {for循环

  if (!root) {二叉树

    return;循环

  }遍历

  path.push_back(root->val);数据

  preOrder(root->left, path);push

  preOrder(root->right, path)path

  path.pop_back(); // 此处回溯递归调用

}return

 

回溯法解决四皇后问题时,push和pop是在for循环里面的,须要循环push和pop四次。

二先序遍历二叉树时,只有一次push和pop。

仔细比较其中的差别在于:

    在二叉树的每一个节点,从行来看只有一个数据,因此只会有一次push和pop的回溯,即使是多叉树,只会影响调用子树的次数;

    而4皇后问题,对于每一行来讲,它其实有4个可选的值,每一个值push和pop构成一次回溯

结论:

    1,回溯的次数取决于节点的行数

    2,树有多少个字节点,就会递归调用几回子树。二叉树只有左右节点

相关文章
相关标签/搜索