【LeetCode算法】第112题：路径总和

本文主要是介绍【LeetCode算法】第112题：路径总和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、题目描述

二、初次解答

三、官方解法

四、总结

---

一、题目描述

二、初次解答

1. 思路：二叉树先序遍历。首先访问根节点，若根节点是叶子节点并且值等于目标值，则返回true，否则递归访问左子树和右子树，只要左子树和右子树的返回值有一个为true即可。

2. 代码：

bool hasPathSum(struct TreeNode* root, int targetSum) {if(!root)return false;if(!root->left && !root->right){return root->val == targetSum;}return hasPathSum(root->left, targetSum-root->val) || hasPathSum(root->right, targetSum-root->val);
}

3. 优点：仅遍历一遍，时间复杂度为O(n)。

4. 缺点：利用了递归，空间复杂度为O(H)。

三、官方解法

官方解法一需要手动维护队列，空间开销更大；官方解法二与上述解法相同。

四、总结

针对二叉树的路径问题，利用二叉树先序遍历的递归方法可以轻松解决。

这篇关于【LeetCode算法】第112题：路径总和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---