면접 문제 29: 두 갈래 나무 중 어떤 값의 경로
두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.수의 뿌리 결점에서 시작하여 잎 노드가 지나가는 결점이 하나의 경로를 형성할 때까지 아래로 내려가다.
사고방식: 경로는 반드시 나무의 뿌리 결점에서 시작해야 한다.
그래서 우리는 귀속으로 할 수 있다.경로를 통과하는 값을 vector로 저장합니다.
사실 이것도 거슬러 올라가는 사상이다. 어떤 결점이 잎 노드나 현재 결점의 값이 경로에 기대치보다 크면 이 노드의 부 노드로 거슬러 올라간다.
거슬러 올라갈 때 현재 추가된 값을 삭제해야 합니다.
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
struct BinaryTreeNode{
int value;
BinaryTreeNode *left;
BinaryTreeNode *right;
BinaryTreeNode(int val) :value(val), left(NULL), right(NULL){}
};
void printPath(vector<int> path)
{
for (int i = 0; i < path.size(); ++i) cout << path[i] << " ";
cout << endl;
}
void recursiveFindPath(BinaryTreeNode *root, int target, vector<int> &path)
{
if (root == NULL) return;
if (root->value > target) return;
path.push_back(root->value);
if (root->value == target) printPath(path);
else
{
recursiveFindPath(root->left, target - root->value, path);
recursiveFindPath(root->right, target - root->value, path);
}
path.pop_back(); //
}
void findPath(BinaryTreeNode *root,int target)
{
if (root == NULL) return;
vector<int> path;
recursiveFindPath(root, target, path);
}
int main()
{
BinaryTreeNode *a = new BinaryTreeNode(10);
BinaryTreeNode *b = new BinaryTreeNode(5);
BinaryTreeNode *c = new BinaryTreeNode(12);
BinaryTreeNode *d = new BinaryTreeNode(4);
BinaryTreeNode *e = new BinaryTreeNode(7);
a->left = b; a->right = c;
b->left = d; b->right = e;
findPath(a, 22);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
