剑指offer - 二叉树中和为某一值的路径

题目

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的跟节点开始往下一直到叶节点所经过的节点形成一条路径。

思路

• 递归前序遍历， 把结点加入路径
• 若该结点是叶子结点则比较当前路径和是否等于期待和，等于期待的和则打印路径，不是则继续执行
• 弹出结点，每一轮递归返回到父结点时，当前路径也应该回退一个结点

分析

比如查找值22，按照前序遍历，很显然先执行根结点10，然后分别操作左子树和右子树，上图满足的路径是10->5->7和10->12

算法实现

#include <iostream>
#include <vector>
using namespace std;

struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
};

void FindPath(BinaryTreeNode *pRoot,
              int expectedSum,
              vector<int> &path,
              int currentSum);


void FindPath(BinaryTreeNode *pRoot, int expectedSum) {
    if (pRoot == nullptr)
        return;
  
    // 使用vector模拟栈存储路径
    vector<int> path;
    int currentSum = 0;
    FindPath(pRoot, expectedSum, path, currentSum);
}

void FindPath(BinaryTreeNode *pRoot,
              int expectedSum,
              vector<int> &path,
              int currentSum) {
    // 计算路径值
    currentSum += pRoot->m_nValue;
    // 存储路径值
    path.push_back(pRoot->m_nValue);

    // 是否是叶子结点
    bool isLeaf = (pRoot->m_pLeft == nullptr && pRoot->m_pRight == nullptr);

    // 有效路径
    if (currentSum == expectedSum && isLeaf) {
        printf("A path is found：");
        // 打印路径
        vector<int>::iterator iter = path.begin();
        for (; iter != path.end(); ++iter)
            printf("%d\t", *iter);
        printf("\n");
    }

    // 继续路径查找
    if (pRoot->m_pLeft != nullptr) {
        FindPath(pRoot->m_pLeft, expectedSum, path, currentSum);
    }
    if (pRoot->m_pRight != nullptr) {
        FindPath(pRoot->m_pRight, expectedSum, path, currentSum);
    }

    // 弹出末尾结点值
    path.pop_back();
}

实现2

class Solution {
    vector<vector<int>> allRes;
    vector<int> tmp;
    void dfsFind(BinaryTreeNode * node , int left){
        tmp.push_back(node->m_nValue);
        // 路径满足
        if(left - node->m_nValue == 0 && !node->m_pLeft && !node->m_pRight)
            allRes.push_back(tmp);
        else {
            if(node->m_pLeft) dfsFind(node->m_pLeft, left - node->m_nValue);
            if(node->m_pRight) dfsFind(node->m_pRight, left - node->m_nValue);
        }
        tmp.pop_back();
    }
public:
    vector<vector<int>> FindPath(BinaryTreeNode* root,int expectNumber) {
        if(root) dfsFind(root, expectNumber);
        return allRes;
    }
};

参考

《剑指offer》
二叉树中和为某一值的路径