算法总结

1.二叉树每层的最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

题解：看见二叉树的题，遍历用深度优先搜索或者广度优先搜索都是有固定模板的，具体看题意，本题可以用深度优先搜索找每一层的最大值

package com.chenghaixiang.jianzhi2.day15;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 程海翔
 * @school 石家庄铁道大学
 */
public class Office044 {
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.left = left;
        this.right = right;
    }
}

class Solution {
    //深度优先搜索
    public List<Integer> largestValues(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        List<Integer> res=new ArrayList<>();
        dfs(res,root,0);
        return res;

    }

    public void dfs(List<Integer> res,TreeNode root,int curHeight){
        //curheight表示的是层数
        //递归先遍历左子树，将当前层的第一个元素添加进链表
        if(curHeight==res.size()){
            res.add(root.val);
        }else {
            //curHeight在链表中表示当前层的下标
            //更新当前层中元素的最大值
            res.set(curHeight,Math.max(res.get(curHeight),root.val));
        }
        if(root.left!=null){
            //curHeight+1层数加1
            dfs(res,root.left,curHeight+1);
        }
        if(root.right!=null){
            dfs(res,root.right,curHeight+1);
        }
        
    }
}

2.二叉树最底层最左边的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

题解：同上，只是拿一个值存放最大层，然后优先递归左子树，当层数是最大时再拿一个值存放val

package com.chenghaixiang.jianzhi2.day15;

/**
 * @author 程海翔
 * @school 石家庄铁道大学
 */
public class Office045 {
}
//给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
//
//假设二叉树中至少有一个节点。
class Solution01 {
    int curVal = 0;
    //记录最大层数
    int curHeight = 0;

    //深度优先遍历
    public int findBottomLeftValue(TreeNode root) {
        int curHeight = 0;
        dfs(root, 0);
        return curVal;
    }

    void dfs(TreeNode root,int height){
        if(root==null){
            return;
        }
        dfs(root.left,height+1);
        dfs(root.right,height+1);
        //当前层数大于最大层数，即当前层数是最底层，因为先遍历的左子树，所以当遍历到右子树时，如果最低层有左右子树，height==curHeight不满足条件不进入条件，所以curVal必是最底层 最左边 节点的值
        if(height>curHeight){
            curHeight=height;
            curVal=root.val;
        }

    }
}