LeetCode-二叉树

前中后遍历（深度优先遍历）

● 递归法：
ⅰ. 确定递归函数的参数和返回值
ⅱ. 确定终止条件
ⅲ. 确定单层递归的条件
● 迭代法：用栈的思想

//递归：前序遍历
class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer>res=new ArrayList<Integer>();
    preorder(root,res);
    return res;
  }
  public void preorder(TreeNode root,List<Integer> res){
    if(root==null){
      return;
    }
    res.add(root.val);
    preorder(root.left,res);
    preorder(root.right,res);
  }
}
//迭代：
//前序遍历：中-左-右，入栈：中-右-左
//后序遍历：左-右-中，入栈：中-左-右，出栈：中-右-左， 翻转结果
//中序遍历：左-中-右，用指针遍历访问左下节点

层序遍历（广度优先遍历：用队列实现）

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
       Deque<TreeNode>que=new LinkedList<>();
       List<List<Integer>>res=new ArrayList<>(); 
       if(root!=null){
        que.add(root);}
       while(!que.isEmpty()){
        int k=que.size();
        List<Integer>tmp=new ArrayList<>();
        for(int i=0;i<k;i++){
            TreeNode node=que.poll();
            tmp.add(node.val);
            if(node.left!=null){
                que.add(node.left);}
            if(node.right!=null){
                que.add(node.right);}}
                    res.add(tmp); }
       return res;}}

层序遍历II

//将每层的结果添加到res的开头反转
   res.add(0, tmp);

二叉树右视图

while (!que.isEmpty()) {
    int k = que.size();
    TreeNode rightmost = null;
    for (int i = 0; i < k; i++) {
       TreeNode node = que.poll();                
        // 更新每层最后一个节点为 rightmost
        rightmost = node;                
        if (node.left != null) {
            que.add(node.left); }                
        if (node.right != null) {
            que.add(node.right);}}            
    // 将每层的最后一个节点值添加到结果
    if (rightmost != null) {
       res.add(rightmost.val);}}

二叉树层平均值

while (!que.isEmpty()) {
            int k = que.size();
            double sum = 0; // 用于累加每层节点的值            
            for (int i = 0; i < k; i++) {
                TreeNode node = que.poll();
                sum += node.val; // 累加节点值                
                if (node.left != null) {
                    que.add(node.left); }     
                if (node.right != null) {
                    que.add(node.right);}}            
            // 计算当前层的平均值并添加到结果
            res.add(sum / k); }

N叉树层序遍历

Deque<Node>queue=new LinkedList<>();//TreeNode为二叉树，这里是N  
queue.addAll(node.children);//注意All大小写

每个数行中最大值

int max = Integer.MIN_VALUE; // 初始化最大值为最小整数
max = Math.max(max, node.val); // 更新当前层的最大值
res.add(max); // 将当前层的最大值添加到结果列表

填充每个节点的下一个右侧节点指针

for (int i = 0; i < k; i++) {
  Node node = que.poll();
  if (i < k - 1) {// 将当前节点next指向同层下一个节点
    node.next = que.peek();
    } return root; // 返回连接后的树的根节点

二叉树最大和最小深度

● minDepth ：在每层中遍历节点时，如果发现当前节点是叶子节点（没有左子树和右子树），则立即返回当前深度
● maxDepth ：在每层中遍历节点时，每次进入 while 循环都会增加深度，并在遍历所有节点后返回深度值

//最大：
int res = 0;
if (root != null) {
que.add(root);}
while (!que.isEmpty()) {
  int k = que.size(); // 当前层的节点数
  res++; // 每次进入循环表示深度增加
  for (int i = 0; i < k; i++) {}
  return res; // 返回树的最大深度 }}

// 最小：如果当前节点是叶子节点，返回当前深度
if (node.left == null && node.right == null) {
  return res;

翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null; }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;}}

对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null)return true;
        return compare(root.left,root.right);
    }
    private boolean compare(TreeNode left,TreeNode right){
        if(left==null&right==null)return true;
        if(left==null||right==null)return false;
        if(left.val!=right.val)return false;
        return compare(left.left,right.right)&&compare(left.right,right.left);
    }}

二叉树最大最小深度（递归）

//最大深度
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)return 0;
        int ldep=maxDepth(root.left);
        int rdep=maxDepth(root.right);
        return Math.max(ldep,rdep)+1;
    }}

//最小深度
class Solution {
    public int minDepth(TreeNode root) {
       if(root==null)return 0;
       if(root.right==null)return minDepth(root.left)+1;
       if(root.left==null)return minDepth(root.right)+1;
       return Math.min(minDepth(root.left),minDepth(root.right))+1;
    }}

平衡二叉树（递归）

● 平衡二叉树：二叉树每个节点的左右两个子树的高度差的绝对值不超过1

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getH(root)!=-1;}
    public int getH(TreeNode node){
        if(node==null)return 0;
        int lh=getH(node.left);
        if(lh==-1)return -1;
        int rh=getH(node.right);
        if(rh==-1)return -1;
        if(Math.abs(lh-rh)>1)return -1;
            return Math.max(lh,rh)+1;   }}

二叉树的所有路径（递归）

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String>res=new ArrayList<>();
        dfs(root,"",res);
        return res;}
    public void dfs(TreeNode root,String path,List<String> res){
        if(root==null)return;
        if(root.left==null&&root.right==null){
            res.add(path+root.val);
            return;}
        dfs(root.left,path+root.val+"->",res);
        dfs(root.right,path+root.val+"->",res);}}

左叶子之和（递归）

● 左叶子：节点A的左孩子不为空，且左孩子的左右孩子都为空

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null)return 0;
        int lv=sumOfLeftLeaves(root.left);
        int rv=sumOfLeftLeaves(root.right);
        if(root.left!=null&&root.left.left==null&&root.left.right==null){
        lv=root.left.val;}
        int sum=lv+rv;
        return sum; }}

完全二叉树的节点个数（递归）

● 完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点

//普通二叉树求法
class Solution {
    public int countNodes(TreeNode root) {
      if(root==null)return 0;
      int l=countNodes(root.left);
      int r=countNodes(root.right);
      return l+r+1; }}

//完全二叉树求法
class Solution {
    public int countNodes(TreeNode root) {
        if(root==null)return 0;
        int ld=0,rd=0;
        TreeNode left=root.left;
        TreeNode right=root.right;
        while(left!=null){
            left=left.left;
            ld++;}
        while(right!=null){
            right=right.right;
            rd++;}
        if(ld==rd) return (2<<ld)-1;
        return countNodes(root.left)+countNodes(root.right)+1;}}

找树左下角的值

//迭代
class Solution {
    public int findBottomLeftValue(TreeNode root) {
     Deque<TreeNode>que=new LinkedList<>();
     int res=0;
     que.offer(root);
     while(!que.isEmpty()){
        int n=que.size();
        for(int i=0;i<n;i++){
            TreeNode node=que.poll();
            if(i==0){
                res=node.val;} 
            if(node.left!=null){
                que.offer(node.left);}
            if(node.right!=null){
                que.offer(node.right);}      
        }}
     return res;}}

//递归
class Solution {
    private int d=-1;
    private int res=0;
    public int findBottomLeftValue(TreeNode root) {
    res=root.val;
    findB(root,0);
    return res;}
    public void findB(TreeNode root,int deep){
        if(root==null)return;
        if(root.left==null&&root.right==null){
            if(d<deep){
                d=deep;
                res=root.val; }}
        if(root.left!=null){
            findB(root.left,deep+1);}
        if(root.right!=null){
            findB(root.right,deep+1); }}}

路径总和

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
    if(root==null)return false;
    if(root.left==null&&root.right==null)return targetSum==root.val;
    return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);
    }}

路径总和Ⅱ

class Solution {
    List<List<Integer>>res=new LinkedList <>();
    Deque<Integer>path=new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        pa(root,targetSum);
        return res;}
    public void pa(TreeNode root,int targetSum){
     if(root==null)return;
     path.offerLast(root.val);
     targetSum-=root.val;
       if(root.left==null&&root.right==null&&targetSum==0)res.add(new LinkedList<Integer>(path));
       pa(root.left,targetSum);
       pa(root.right,targetSum);
       path.pollLast();}}

构造二叉树中后

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n=inorder.length;
        Map<Integer,Integer>res=new HashMap<>(n);
        for(int i=0;i<n;i++){
            res.put(inorder[i],i);}
       return kd(inorder,0,n,postorder,0,n,res); }
    public TreeNode kd(int[] inorder,int inl,int inr,int[] postorder,int postl,int postr,Map <Integer,Integer>res){
        if(postl==postr)return null;
        int ls=res.get(postorder[postr-1])-inl;
        TreeNode left=kd(inorder,inl,inl+ls,postorder,postl,postl+ls,res);
        TreeNode right=kd(inorder,inl+ls+1,inr,postorder,postl+ls,postr-1,res);
        return new TreeNode(postorder[postr-1],left,right);}}

构造二叉树前中

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n=preorder.length;
        Map<Integer,Integer>res=new HashMap<>(n);
        for(int i=0;i<n;i++){
            res.put(inorder[i],i);}
       return kd(inorder,0,n,preorder,0,n,res);}
    public TreeNode kd(int[] inorder,int inl,int inr,int[] preorder,int prel,int prer,Map <Integer,Integer>res){
        if(prel==prer)return null;
        int ls=res.get(preorder[prel])-inl;
        TreeNode left=kd(inorder,inl,inl+ls,preorder,prel+1,prel+ls+1,res);
        TreeNode right=kd(inorder,inl+ls+1,inr,preorder,prel+ls+1,prer,res);
        return new TreeNode(preorder[prel],left,right);}}