二叉树中和为某一值的路

本文主要是介绍二叉树中和为某一值的路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意描述：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。如：
        10
        /    \
      5    12
    /   \

  4    7

解题思路：借助栈，进行深度优先遍历，如果当前结点为叶子结点并且从根结点到当前结点的值的和等于给定值，则找到一条路径并打印，否则继续向叶结点遍历或者返回上一级，返回上一级时需要在当前计算的和的基础上减去当前结点的值

（C++版本）

struct BinaryTreeNode {int m_nValue;BinaryTreeNode* m_pLeft;BinaryTreeNode* m_pRight;
};//创建二叉树结点
BinaryTreeNode* CreateBinaryTreeNode(int value) {BinaryTreeNode* pNode = new BinaryTreeNode();pNode->m_nValue = value;pNode->m_pLeft = NULL;pNode->m_pRight = NULL;return pNode;
}//连接二叉树结点
void ConnectionTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight) {if (pParent != NULL) {pParent->m_pLeft = pLeft;pParent->m_pRight = pRight;}
}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 == NULL) && (pRoot->m_pRight == NULL);if (isLeaf && (currentSum == expectedSum)) {cout << "A path is found: ";//vector<int>::iterator it = path.begin();//for (; it != path.end(); ++it)//	cout << *it << " ";for (vector<int>::size_type i = 0; i < path.size(); i++)cout << path[i] << " ";cout << endl;}//如果不是叶结点if (pRoot->m_pLeft != NULL)findPath(pRoot->m_pLeft, expectedSum, path, currentSum);if (pRoot->m_pRight != NULL)findPath(pRoot->m_pRight, expectedSum, path, currentSum);//在返回父结点之前，在路径上删除当前结点path.pop_back();
}void findPath(BinaryTreeNode* pRoot, int expectedSum) {if (pRoot == NULL)return;vector<int> path;int currentSum = 0;findPath(pRoot, expectedSum, path, currentSum);
}//先序遍历
void InOrder(BinaryTreeNode* pTreeRoot) {	if (pTreeRoot->m_pLeft != NULL)InOrder(pTreeRoot->m_pLeft);cout << pTreeRoot->m_nValue << " ";if (pTreeRoot->m_pRight != NULL)InOrder(pTreeRoot->m_pRight);
}int main()
{BinaryTreeNode* node1 = CreateBinaryTreeNode(10);BinaryTreeNode* node2 = CreateBinaryTreeNode(5);BinaryTreeNode* node3 = CreateBinaryTreeNode(12);BinaryTreeNode* node4 = CreateBinaryTreeNode(4);BinaryTreeNode* node5 = CreateBinaryTreeNode(7);ConnectionTreeNodes(node1, node2, node3);ConnectionTreeNodes(node2, node4, node5);InOrder(node1);cout << endl;findPath(node1, 22);return 0;
}

（Java版本）

class BinaryTreeNode{int value;BinaryTreeNode leftNode;BinaryTreeNode rightNode;
}public class FindPath {		//解题思路：借助栈，进行深度优先遍历，如果当前结点为叶子结点并且从根结点到当前结点的值的和等于给定值，则找到一条路径并打印//否则继续向叶结点遍历或者返回上一级，返回上一级时需要在当前计算的和的基础上减去当前结点的值public static void findPath(BinaryTreeNode root, int expectedSum){if(root == null)return;Stack<Integer> stack = new Stack<Integer>();int currentSum = 0;findPath(root, currentSum, stack, expectedSum);}public static void findPath(BinaryTreeNode root,int currentSum, Stack<Integer> path, int expectedSum){currentSum += root.value;path.add(root.value);//如果是叶结点，并且路径上结点的和等于输入的值则打印boolean isLeaf = (root.leftNode==null)&&(root.rightNode==null);if(isLeaf && (currentSum == expectedSum)){System.out.print("A path find: ");for(int n : path)System.out.print(n + " ");System.out.println();}//如果不是叶结点if(root.leftNode != null)findPath(root.leftNode, currentSum, path, expectedSum);if(root.rightNode != null)findPath(root.rightNode, currentSum, path, expectedSum);//在返回父结点之前把路径上的当前结点删除path.pop();}public static void main(String[] args) {BinaryTreeNode root = new BinaryTreeNode();BinaryTreeNode node1 = new BinaryTreeNode();BinaryTreeNode node2 = new BinaryTreeNode();BinaryTreeNode node3 = new BinaryTreeNode();BinaryTreeNode node4 = new BinaryTreeNode();root.leftNode = node1;root.rightNode = node2;node1.leftNode = node3;node1.rightNode = node4;root.value = 10;node1.value = 5;node2.value = 12;node3.value = 4;node4.value = 7;findPath(root, 22);}}

（Golang版本）

package mainimport (list2 "container/list""fmt"
)// 二叉树结构
type BTree struct {Val   intLeft  *BTreeRight *BTree
}// 构建一棵二叉树
//      8
//    /   \
//   6     10
//  / \    / \
// 5   7  9   11
func newBTree() *BTree {node2_1 := &BTree{Val: 5}node2_2 := &BTree{Val: 7}node2_3 := &BTree{Val: 9}node2_4 := &BTree{Val: 11}node1_1 := &BTree{Val: 6, Left: node2_1, Right: node2_2}node1_2 := &BTree{Val: 10, Left: node2_3, Right: node2_4}root := &BTree{Val: 8, Left: node1_1, Right: node1_2}return root
}/** 求二叉树和为某值的所有路径*/
func findPath(root *BTree, expSum int) {if root == nil {return}path := newStack()curSum := 0solution(root, curSum, expSum, path)
}
func solution(root *BTree, curSum, expSum int, path *myStack) {curSum += root.Valpath.push(root)if root.Left == nil && root.Right == nil && curSum == expSum {for ele := path.List.Front(); ele != nil ; ele = ele.Next()  {node := ele.Value.(*BTree)fmt.Printf("%d\t", node.Val)}fmt.Println()}if root.Left != nil {solution(root.Left, curSum, expSum, path)}if root.Right != nil {solution(root.Right, curSum, expSum, path)}path.pop()
}func main() {root := newBTree()findPath(root, 21)
}/
// 自定义栈
type myStack struct {List *list2.List
}func newStack() *myStack {stack := myStack{List: list2.New()}return &stack
}func (stack *myStack) push(ele interface{}) {stack.List.PushBack(ele)
}func (stack *myStack) pop() interface{} {if ele := stack.List.Back(); ele != nil {stack.List.Remove(ele)return ele.Value}return nil
}func (stack *myStack) len() int {return stack.List.Len()
}// 自定义队列
type myQueue struct {List *list2.List
}func newQueue() *myQueue {queue := myQueue{List: list2.New()}return &queue
}func (queue *myQueue) push(ele interface{}) {queue.List.PushBack(ele)
}func (queue *myQueue) pop() interface{} {if ele := queue.List.Front(); ele != nil {queue.List.Remove(ele)return ele.Value}return nil
}func (queue *myQueue) len() int {return queue.List.Len()
}

 

 

 

 

 

这篇关于二叉树中和为某一值的路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---