Day 69

第106题:

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:你可以假设树中没有重复的元素。

1、中序遍历是先遍历左子树,在遍历根节点,最后右子树;

后序遍历是先遍历左子树,再右子树,最后根节点;

这样可知后序遍历序列中的最后那个元素就是树的根节点;

再寻找中序遍历中这个节点位置,将中序遍历分成两部分,其中左边那部分就是根节点的左子树,右边那部分就是根节点的右子树;

直到了左右子树的范围就按照上面的步骤递归创建树即可。

第105题:

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:你可以假设树中没有重复的元素。

1、前序遍历是先便利根节点,再遍历左子树,最后右子树;

中序遍历是先遍历左子树,再遍历根节点,最后右子树;

那么前序遍历的第一个元素就是整棵树的根节点,根据这个节点可以将中序遍历分成左子树和右子树两部分;、

然后根据上面的原则分别递归找出左子树和右子树的根节点,依次递归下去,得出整棵树结构。

第129题:

给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。

例如,从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。来源:力扣(LeetCode)

说明: 叶子节点是指没有子节点的节点。

1、深度优先遍历来求每条根节点到叶子节点的和;

利用递归求出值。

2、利用两个队列node和value来存储对应的节点和值,当节点是叶子节点时,就将值加入到结果中。

value每次加入的是上面层叠的节点数字之和*10+自身的数字;

判断出队列的节点是叶子节点,就将对应的值加入res中,最后得出总和。

原文地址:https://www.cnblogs.com/liang-yi-/p/13733189.html