代码随想录Day15 二叉树 LeetCodeT513 找树左下角的值 T112路径总和 T106 从中序和后序遍历构造二叉树

以上思路来自于:代码随想录 (programmercarl.com)

LeetCode T513 找树左下角的值

题目思路:

本题思路:这题我们使用递归法和迭代法解决问题

注意:左下角的值不一定就是一直向左遍历的叶子结点的值,首先可以确定是最后一行的第一个叶子结点的值,也就是最大深度的叶子结点的值

定义最大深度Deep变量,返回值result

1.递归法

前序遍历为例

1.1 确定递归的返回值和参数类型

我们这里不需要返回值,传入参数是节点和深度

void travelsal(TreeNode node,int deep)

1.2 确定终止条件

这里我们遇到一次叶子结点就更新一次最大深度,并记录下该节点的val

     if(node.left == null && node.right == null)
        {
            if(deep>Deep)
            {
                Deep = deep;
                result = node.val;
            }
           
        }

1.3 实现一次递归

    if(node.left != null)
        {
            travelsal(node.left,deep+1);
 
        }
        if(node.right != null)
        {
            travelsal(node.right,deep+1);
        }

2.迭代法

思路:使用层序遍历,找到最后一行,记录下最左边节点的数值

1.使用队列结构,队列不为空就继续,先加入根节点,接着我们用一个临时节点记录一下正在遍历的节点,方便取值,使用for循环,遍历每一层,记录下每一层第一个值,如果不是叶子节点就继续入队,详细思路可以看 层序遍历章节

代码解析:

public int findBottomLeftValue(TreeNode root) {
        //迭代法
       int result = 0;
       Queue que = new LinkedList<>();
       que.offer(root);
       while(!que.isEmpty())
       {
           int size = que.size();
           for(int i = 0;i
           {
               TreeNode tmp = que.poll();
               if(i == 0)
               {
                   result = tmp.val;
               }
               if(tmp.left != null)
               {
                  que.offer(tmp.left);
               }
               if(tmp.right != null)
               {
                   que.offer(tmp.right);
               }
           }
 
       }
       return result;
 
    }
}

题目代码:

class Solution {
    int Deep = -1;
    int result = 0;
    public int findBottomLeftValue(TreeNode root) {
        result = root.val;
        travelsal(root,0);
        return result;
       
 
    }
    void travelsal(TreeNode node,int deep)
    {
        if(node == null)
        {
            return;
        } 
        if(node.left == null && node.right == null)
        {
            if(deep>Deep)
            {
                Deep = deep;
                result = node.val;
            }
           
        }
        if(node.left != null)
        {
            travelsal(node.left,deep+1);
 
        }
        if(node.right != null)
        {
            travelsal(node.right,deep+1);
        }
 
    }
}

LeetCode T112 路径总和

题目链接:112. 路径总和 - 力扣（LeetCode）

题目思路:

思路其实很简单,我们只需要遍历二叉树在叶子节点的时候判断即可,但是还是有很多细节需要注意,我们分一下几步操作,判断节点是否为空,减去该节点的值,判断叶子结点的值,下面就是递归的过程

1.判断头结点

    if(root == null)
        {
            return false;
        }

2.叶子节点

        //叶子结点
        if(root.left == null && root.right == null)
        {
            return targetSum == 0;
        }

3.递归过程

         //递归逻辑
        if(root.left != null)
        {
            boolean left = hasPathSum(root.left,targetSum);
            if(left)
            {
                return true;
            }
        }
        if(root.right != null)
        {
            boolean right = hasPathSum(root.right,targetSum);
            if(right)
            {
                return true;
            }
        }

注:我们这里用目标值一直往下减,如果到叶子节点发现值减到0就说明成功了,注意回溯的过程这里省略了.

题目代码:

class Solution {  
    public boolean hasPathSum(TreeNode root, int targetSum) {  
        //终止条件
        if(root == null)
        {
            return false;
        }
        targetSum -= root.val;
        //叶子结点
        if(root.left == null && root.right == null)
        {
            return targetSum == 0;
        }
        //递归逻辑
        if(root.left != null)
        {
            boolean left = hasPathSum(root.left,targetSum);
            if(left)
            {
                return true;
            }
        }
        if(root.right != null)
        {
            boolean right = hasPathSum(root.right,targetSum);
            if(right)
            {
                return true;
            }
        }
        return false;
 
    }  
}

T106 从中序和后序遍历构造二叉树

题目链接:106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

题目思路:

这题思路较为简单,代码较长,我们举一个例子

我们首先根据后序的左右中来切割中序数组,就能知道9是左子树,15 20 7是右子树

然后根据右子树判断中节点是20,20的左节点是15右节点是7,我们就能唯一确定一个二叉树

这里我们分为以下几步处理

1.创建一个map来便于查找

2.将inorder的数据保存到map中 (key是数值,value是下标)

3.接着我们使用递归来实现

4.确定参数和返回值

public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) 

5.终止条件(注意这里切分区间要统一,使用闭区间还是左开右闭区间)

 if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }

6.单次递归

        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);

题目代码:

class Solution {
    Map map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for(int i = 0;i
        {
            map.put(inorder[i],i);
        }
        return FindOrder(inorder,0,inorder.length,postorder,0,postorder.length);
 
    }
    public TreeNode FindOrder(int[] inOrder,int inBegin,int inEnd,int[] postOrder,int postBegin,int postEnd)
    {
        //结束条件,这里我使用左闭右开写
        if(inBegin>=inEnd || postBegin>=postEnd)
        {
            return null;
        }
        //找到后序在中序的位置
        int index = map.get(postOrder[postEnd - 1]);
        //构造节点
        TreeNode root = new TreeNode(inOrder[index]);
        //保存中序左子树的个数,用来确定后序的区间
        int lenOfLeft = index - inBegin;
        root.left = FindOrder(inOrder,inBegin,index,postOrder,postBegin,postBegin+lenOfLeft);
        root.right = FindOrder(inOrder,index+1,inEnd,postOrder,postBegin+lenOfLeft,postEnd-1);
        return root;
    }
}