2代码随想录训练营第十八天 | （递归法实现）找树左下角的值&&路径总和&&路径总和II&&（！！）从中序和后序遍历序列构造二叉树&&（缺）从前序和中序遍历序列构造二叉树

513.找树左下角的值

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

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

【思路】

二编：一开始的想法是采用深度遍历，但是这样的话会很难判断是不是最下层的值。深度遍历行不通，所以我们采用层序遍历。

用层序遍历，循环遍历获得每一层的第0位，最后赋值的即最后一层（左下角）的值。

• Java实现

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        int res =0;
        queue.add(root);
        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实现

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. 路径总和

【思路】

二编：回溯！这样就知道是不是了！

递归

1.确定递归函数的参数和返回类型

参数：需要二叉树的根节点，还需要一个计数器，用来计算二叉树的一条边之和是否正好是目标和。

递归函数什么时候需要返回值？

• 当需要搜索整颗二叉树且不用处理递归返回值，递归函数就不需要返回值。
• 当需要搜索整颗二叉树且需要处理递归返回值，递归函数就需要返回值。
• 当要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了要及时返回（本题情况）

2.确定终止条件

不要去累加然后判断是否等于目标和，这样很难带数字进入下一层。因此我们采用递减，每次减去遍历路径节点上的数值。

如果最后count == 0 ，同时到达了叶子节点的话，说明找到了目标和、

3.确定单层递归的逻辑

因为终止条件是判断叶子节点，所以递归的过程就不要让空节点进入递归了。

递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。

---

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

• Java实现

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即可

  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，即说明这条路径上所有节点值相加等于目标和。

  /**
   * 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实现

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

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 ArrayList<>();
        
        traversal(root,res,path,targetSum);
        return res;
    }

    public void traversal(TreeNode node,List<List<Integer>> res ,List<Integer> path,int targetSum){
        path.add(node.val);
        if(node.left == null && node.right == null){
            if(targetSum == node.val){
                //!!该path是新创建了一个对象，复制了当前path的值
                res.add(new ArrayList<>(path));
                //res.add(new ArrayList<>(path)); path会在接下来的操作中不断改动
            }
            return ;
        }
        //要记得回溯
        if(node.left != null){
            traversal(node.left,res,path,targetSum-node.val);
            path.remove(path.size()-1);
        }
        if(node.right != null){
            traversal(node.right,res,path,targetSum-node.val);
            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)
  }

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实现

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实现

 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实现

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实现

 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的具体计算，还需要复盘一下。