513.找树左下角的值

文章:16. 找树左下角的值

题目:513. 找树左下角的值

【思路】

用层序遍历,循环遍历获得每一层的第0位,最后赋值的即最后一层(左下角)的值

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int res = 0;
while(!queue.isEmpty()){
int len = queue.size();
for(int i = 0;i<len;i++){//循环边缘找错了
TreeNode node = queue.poll();
if(i==0)res = node.val;
if(node.left!=null)queue.add(node.left);
if(node.right != null)queue.add(node.right);
}
}
return res;
}
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func findBottomLeftValue(root *TreeNode) int {
res :=0
curLevel := []*TreeNode{root}
for len(curLevel)>0{
nextLevel :=[]*TreeNode{}
for index,node := range curLevel{
if index == 0{
res = node.Val
}
if node.Left!=nil{
nextLevel = append(nextLevel,node.Left)
}
if node.Right!=nil{
nextLevel = append(nextLevel,node.Right)
}
}
curLevel = nextLevel
}
return res
}

112.路径总和

文章:17. 路径总和

题目:112. 路径总和

【思路】

使用递归的方法,将targetSum转化为每层减去相应的node.val,这样只需要判断最后targetSum是否等于当前层的node.val即可

  • Java实现
1
2
3
4
5
6
7
8
9
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root ==null)return false;
if(root.left == null && root.right==null && targetSum==root.val){
return true;
}
return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
}
}
  • Go实现

    • 未省略版:每层的val已经被提前减去了,最后只需要判断==0即可
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    func hasPathSum(root *TreeNode, targetSum int) bool {
    var traversal func(node *TreeNode ,res int)bool
    traversal = func(node *TreeNode,count int) bool{
    if node ==nil{
    return false
    }
    //确定终止条件
    if node.Left == nil &&node.Right ==nil &&count ==0{
    return true
    }
    if node.Left==nil &&node.Right==nil{
    return false
    }
    //确定单层递归的逻辑
    if node.Left!=nil{
    if traversal(node.Left,count-node.Left.Val){
    return true
    }
    }
    if node.Right!=nil{
    if traversal(node.Right,count-node.Right.Val){
    return true
    }
    }
    return false
    }
    return traversal(root,targetSum)

    }
    • 省略版:当最后一层(叶子节点)的值==targetSum,即说明这条路径上所有节点值相加等于目标和。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /**
    * Definition for a binary tree node.
    * type TreeNode struct {
    * Val int
    * Left *TreeNode
    * Right *TreeNode
    * }
    */
    func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil{
    return false
    }

    if(root.Left==nil&&root.Right == nil &&targetSum == root.Val){
    return true
    }
    return hasPathSum(root.Left,targetSum -root.Val) || hasPathSum(root.Right,targetSum-root.Val)

    }

113.路径总和II

文章:17. 路径总和

题目:113. 路径总和 II

【思路】

113.路径总和II需要遍历整个树,找到所有路径,所以递归函数不要返回值

  • Java实现

    回溯算法需要注意递归之后需要去除当前节点的值,不然会把二叉树内所有的路径都遍历一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
if(root==null)return res;
List<Integer>path = new LinkedList<>();
preorderdfs(root,targetSum,res,path);
return res;
}
public void preorderdfs(TreeNode node,int targetSum ,List<List<Integer>>res,List<Integer>path){
path.add(node.val);
if(node.left==null && node.right == null){
if(targetSum - node.val == 0){
res.add(new ArrayList<>(path));
}
return;
}
if(node.left!=null){
preorderdfs(node.left,targetSum-node.val,res,path);
path.remove(path.size()-1); //回溯
}
if(node.right!=null){
preorderdfs(node.right,targetSum-node.val,res,path);
path.remove(path.size()-1);
}
}
}
  • Go实现

    if node.Left == nil && node.Right == nil && targetSum == 0{
    //不能直接将currPath放到res里面,因为currPath是共享的,指针指向的是同一个地址,每次遍历子树时都会被修改
    copyPath := make([]int,len(*currPath))
    for i,path := range *currPath{
    copyPath[i]=path
    }
    *res = append(*res,copyPath)
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func pathSum(root *TreeNode, targetSum int) [][]int {
res := make([][]int,0)
traverse(root,&res,new([]int),targetSum)
return res
}

func traverse(node *TreeNode,res *[][]int,currPath *[]int,targetSum int){
if node == nil{
return
}
targetSum -= node.Val
*currPath = append(*currPath,node.Val)
if node.Left == nil && node.Right == nil && targetSum == 0{
//不能直接将currPath放到res里面,因为currPath是共享的,指针指向的是同一个地址,每次遍历子树时都会被修改
copyPath := make([]int,len(*currPath))
for i,path := range *currPath{
copyPath[i]=path
}
*res = append(*res,copyPath)
}
traverse(node.Left,res,currPath,targetSum)
traverse(node.Right,res,currPath,targetSum)
*currPath = (*currPath)[:len(*currPath)-1]
}

106.从中序与后序遍历序列构造二叉树

文章:18. 从中序与后序遍历序列构造二叉树

题目:106. 从中序与后序遍历序列构造二叉树

视频:坑很多!来看看你掉过几次坑 | LeetCode:106.从中序与后序遍历序列构造二叉树_哔哩哔哩_bilibili

【思路】

第一步:如果数组大小为0的话,说明是空节点。
第二步:如果不为空,那么取后序数组最后一个元素作为节点元素。
第三步:找到后序遍历最后一个元素在中序数组的位置,作为切割点
第四步:切割中序数组,切成中序左数组和中序右数组(一定是先切中序数组)
第五步:切割后序数组 切好后序左数组和后序右数组
第六步:递归处理左区间和右区间

切割中序数组和后序数组最关键的是要确定好切割的四个区间,坚持循环不变量原则。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
Map<Integer,Integer>map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
map =new HashMap<>();
for(int i =0;i < inorder.length;i++){
map.put(inorder[i],i);
}
return findNode(inorder,0,inorder.length,postorder,0,postorder.length);
}
public TreeNode findNode(int[] inorder,int inBegin,int inEnd,int[] postorder,int poBegin,int poEnd){
if(inBegin>= inEnd || poBegin>= poEnd){
return null;
}
int rootIndex=map.get(postorder[poEnd-1]);
TreeNode root = new TreeNode(inorder[rootIndex]);//构造节点
int lenOfLeft = rootIndex-inBegin;
//左子树,获得中序遍历里面的左中序区间
root.left=findNode(inorder,inBegin,rootIndex,postorder,poBegin,poBegin+lenOfLeft);
//右子树,获得中序遍历里面的右中序区间
root.right = findNode(inorder,rootIndex+1,inEnd,postorder,poBegin+lenOfLeft,poEnd-1);
return root;

}
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 var(
hash map[int]int
)
func buildTree(inorder []int, postorder []int) *TreeNode {
hash = make(map[int]int)
for i, v := range inorder{
hash[v] = i
}
root := rebuild(inorder,postorder,len(postorder)-1,0,len(inorder)-1)
return root
}
//rootIdx表示根节点在后序数组中的索引,l,r表示在中序数组中的前后切分点
func rebuild(inorder []int,postorder []int,rootIdx int,l,r int){
if l > r {
return nil
}
if l == r{
return &TreeNode{Val: inorder[l]}
}

rootV := postorder[rootIdx] //找到根节点的值
index := hash[rootV] //找到中序遍历中对应值的位置
//构造新节点
root := &TreeNode{Val: rootV}
//看不懂怎么分割的数组
root.Left = rebuild(inorder,postorder,rootIdx-(r - index) -1,l,index-1)
rot.Right = rebuild(inorder,postorder,rootIdx-1,index+1,r)
}

105.从前序与中序遍历序列构造二叉树

文章:18. 从中序与后序遍历序列构造二叉树

题目:105. 从前序与中序遍历序列构造二叉树

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
Map<Integer,Integer>map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for(int i = 0 ;i < inorder.length;i++){
map.put(inorder[i],i);
}
return findNode(preorder,0,preorder.length,inorder,0,inorder.length);
}

public TreeNode findNode(int[] preorder,int preStart,int preEnd,int[]inorder,int inStart,int inEnd){
if(preStart >= preEnd || inStart >= inEnd){
return null;
}
int rootIndex = map.get(preorder[preStart]);
TreeNode root = new TreeNode(inorder[rootIndex]);
int lenOfLeft = rootIndex - inStart;
root.left = findNode(preorder,preStart+1,preStart+lenOfLeft+1,inorder,inStart,rootIndex);
root.right = findNode(preorder,preStart+lenOfLeft+1,preEnd,inorder,rootIndex+1,inEnd);
return root;
}
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 var(
hash map[int]int
)
func buildTree(preorder []int, inorder []int) *TreeNode {
hash = make(map[int]int,len(inorder))
for i,v :=range inorder{
hash[v] = i
}
root := traversal(preorder,inorder,0,0,len(inorder)-1)
return root
}
func traversal(preorder []int ,inorder []int ,root int,l,r int)*TreeNode{
if l > r {
return nil
}

rootVal := preorder[root]
index := hash[rootVal]
node := &TreeNode {Val: rootVal}

node.Left=traversal(preorder,inorder,root+1,l,index-1)
node.Right=traversal(preorder,inorder,root+(index-l)+1,index+1,r)
return node
}

【算法总结】

  • 找树左下角的值:采用层次遍历即可
  • 路径总和&II:需要分清楚什么时候递归需要/不需要返回值,遍历整个二叉树就不用返回值。
  • 中序和后序遍历序列构造二叉树&&前序和中序序列构造二叉树:这两题还不是很理解rootIdx的具体计算,还需要复盘一下。