【数据结构与算法面试题】二叉树路径查找

迈不过友情╰ 2022-10-07 03:53 182阅读 0赞

> 题目来源“[数据结构与算法面试题80道][80]”。  
> ![这里写图片描述][850ae70e215a135386d1a92127e69abf.png]

问题分析：核心是树的遍历，注意题目中“路径”的定义，是从根节点到叶子节点。先序遍历正好是从根节点开始，因此可以利用先序遍历的过程来实现这个过程。

方法：

void print_vector(vector<BinaryTreeNode *> &v){
    	vector<BinaryTreeNode *>::iterator it;
    	for (it = v.begin(); it != v.end(); it ++){
    		printf("%d\t", (*it)->m_nValue);
    	}
    	printf("\n");
    }
    
    void pre_order_route(BinaryTreeNode *p, int num, vector<BinaryTreeNode *> &q, int &current){
    	if (NULL == p) return;
    
    	current += p->m_nValue;
    	q.push_back(p);
    
    	bool is_leaf = (NULL == p->m_pLeft) && (NULL == p->m_pRight);
    
    	if (current == num && is_leaf){
    		print_vector(q);
    	}
    	
    	if (NULL != p->m_pLeft){
    		pre_order_route(p->m_pLeft, num, q, current);
    	}
    
    	if (NULL != p->m_pRight){
    		pre_order_route(p->m_pRight, num, q, current);
    	}
    	
    	current -= (*(q.end() - 1))->m_nValue;
    	q.pop_back();
    }
    
    
    void print_route(BinaryTreeNode *root, int num){
    	vector<BinaryTreeNode *> q;// 用队列保存已经访问过的节点
    	int current = 0;
    	pre_order_route(root, num, q, current);
    }

[80]: https://yq.aliyun.com/articles/40478?utm_content=m_15768
[850ae70e215a135386d1a92127e69abf.png]: /images/20221005/cb495e5f609848db9a48c7630b131d41.png