BM26 求二叉树的层序遍历

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList();
        if (root == null) return res;
        //使用队列存储，进行层序遍历
        Queue<TreeNode> q = new ArrayDeque<TreeNode>();
        q.add(root);//将root插入到队列的末尾
        while (!q.isEmpty()) {
            //记录二叉树的某一行
            ArrayList<Integer> row = new ArrayList();
            int n = q.size();
            //因先进入队列的是根节点，故每层节点多少，队列大小就是多少
            for (int i = 0; i < n; i++) {
                TreeNode cur = q.poll(); //出，同时记录cur节点
                row.add(cur.val);
                //若左右孩子存在，则存入左右孩子作为下一次层次
                if (cur.left != null) q.add(cur.left);
                if (cur.right != null) q.add(cur.right);
            }
            //每一层加入
            res.add(row);
        }
        return res;
    }
}

BM27 按之字形顺序打印二叉树

import java.util.ArrayList;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.Collections;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null) return res;
        //使用队列存储，进行层序遍历
        Queue<TreeNode> q = new ArrayDeque<TreeNode>();

        q.add(pRoot);//先将头节点放入
        boolean flag = false;
        while (!q.isEmpty()) {
            ArrayList<Integer> row = new ArrayList<>();
            int n = q.size();

            for (int i = 0; i < n; i++) {
                TreeNode cur = q.poll();//弹出q，并记录
                row.add(cur.val);//存入值

                //看是否有左右还在
                if (cur.left != null) q.add(cur.left);
                if (cur.right != null) q.add(cur.right);
            }
            //要实现奇数层从左到由，偶数层从右到左,即偶数时要逆序q队列
            if (flag) Collections.reverse(row);
            flag = !flag;
            res.add(row);
        }
        return res;
    }

}

BM28 二叉树的最大深度

层序法 空间复杂度O(1),时间复杂度 O*(*n)

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here

        if (root == null) return 0;
        //使用队列存储，进行层序遍历
        Queue<TreeNode> q = new ArrayDeque<TreeNode>();
        q.add(root);//将root插入到队列的末尾
        int h = 0;
        while (!q.isEmpty()) {
            //记录二叉树的某一行
            ArrayList<Integer> row = new ArrayList();
            int n = q.size();
            //因先进入队列的是根节点，故每层节点多少，队列大小就是多少
            for (int i = 0; i < n; i++) {
                TreeNode cur = q.poll(); //出，同时记录cur节点
                row.add(cur.val);
                //若左右孩子存在，则存入左右孩子作为下一次层次
                if (cur.left != null) q.add(cur.left);
                if (cur.right != null) q.add(cur.right);
            }
            h++;
        }
        return h;
    }
}

递归法 O(2^h)

  public int maxDepth (TreeNode root) {
        //使用递归法则需要，分别计算左右子数中最高的值
        if (root == null) return 0;
        int leftH =  maxDepth(root.left);
        int rightH = maxDepth(root.right);
        return leftH > rightH ? (leftH + 1) : (rightH + 1);
    }	

BM29 二叉树中和为某一值的路径(一)

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        // //执行思路，使用dfs遍历每个，同时变化sum，找到满足的值就返回真
        // if(root == null) return false;
        // //叶子路径，且路径和为sum
        // if(root.left==null&&root.right==null&&sum-root.val == 0){
        //     return true;
        // }
        // //递归进去子节点
        // return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
        if (root == null) return false;
        return dfs(root, sum, 0);// 深度优先遍历
    }

    private boolean dfs(TreeNode root, int sum, int res) {
        if (root == null) return false;
        //迭代目标值
        res += root.val;
        // 当当前节点为叶子节点并且目标路径存在时，返回 true
        if (res == sum && root.left == null && root.right == null) {
            return true;
        }
        // 对左右分支进行 dfs
        return dfs(root.left, sum, res) || dfs(root.right, sum, res);
    }
}

BM30 二叉搜索树与双向链表

二叉搜索树是一种特殊的二叉树，它的每个节点值大于它的左子节点，且大于全部左子树的节点值，小于它右子节点，且小于全部右子树的节点值。因此二叉搜索树一定程度上算是一种排序结构。

思路：

二叉搜索树最左端的元素一定最小，最右端的元素一定最大，符合“左中右”的特性，因此二叉搜索树的中序遍历就是一个递增序列，我们只要对它中序遍历就可以组装称为递增双向链表。

具体做法：

• step 1：创建两个指针，一个指向题目中要求的链表头（head），一个指向当前遍历的前一节点（pre)。
• step 2：首先递归到最左，初始化head与pre。
• step 3：然后处理中间根节点，依次连接pre与当前节点，连接后更新pre为当前节点。
• step 4：最后递归进入右子树，继续处理。
• step 5：递归出口即是节点为空则返回。

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    //返回第一个指针，即最小值，先定为null
    public TreeNode head = null;
    //中序遍历当前值的上一位，初值为最小值，先定为null
    public TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            //中序递归，叶子为空则返回
            return null;
        }
        //首先递归到最左最小值
        Convert(pRootOfTree.left); //左

        //中
        //找到最小值，初始化head和pre;
        if (pre == null) {
            head = pRootOfTree;
            pre = pRootOfTree;
        } else {
            //当前节点与上一结点建立连接，将pre设置为当前值
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }

        Convert(pRootOfTree.right); //右
        return head;

    }
}

BM31 对称的二叉树

思路：

前序遍历的时候我们采用的是“根左右”的遍历次序，如果这棵二叉树是对称的，即相应的左右节点交换位置完全没有问题，那我们是不是可以尝试“根右左”遍历，按照轴对称图像的性质，这两种次序的遍历结果应该是一样的。

不同的方式遍历两次，将结果拿出来比较看起来是一种可行的方法，但也仅仅可行，太过于麻烦。我们不如在遍历的过程就结果比较了。而遍历方式依据前序递归可以使用递归：

• 终止条件： 当进入子问题的两个节点都为空，说明都到了叶子节点，且是同步的，因此结束本次子问题，返回true；当进入子问题的两个节点只有一个为空，或是元素值不相等，说明这里的对称不匹配，同样结束本次子问题，返回false。
• 返回值： 每一级将子问题是否匹配的结果往上传递。
• 本级任务： 每个子问题，需要按照上述思路，“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，一起进入子问题，需要两边都是匹配才能对称。

具体做法：

• step 1：两种方向的前序遍历，同步过程中的当前两个节点，同为空，属于对称的范畴。
• step 2：当前两个节点只有一个为空或者节点值不相等，已经不是对称的二叉树了。
• step 3：第一个节点的左子树与第二个节点的右子树同步递归对比，第一个节点的右子树与第二个节点的左子树同步递归比较。

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        return recursion(pRoot, pRoot);
    } 
    public boolean recursion(TreeNode root1, TreeNode root2) {
        //可以两个都为空
        if (root1 == null && root2 == null)
            return true;
        //只有一个为空或者节点值不同，必定不对称
        if (root1 == null || root2 == null || root1.val != root2.val)
            return false;
        //每层对应的节点进入递归比较
        return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
    }
}

BM32 合并二叉树

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param t1 TreeNode类
     * @param t2 TreeNode类
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        //思路：同时遍历左右，相同就加上，为空就指向
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        //根左右遍历
        TreeNode head = new TreeNode(t1.val + t2.val);
        head.left = mergeTrees(t1.left, t2.left);
        head.right = mergeTrees(t1.right, t2.right);
        return head;
    }
}

BM34 判断是不是二叉搜索树

思路：

二叉搜索树的特性就是中序遍历是递增序。既然是判断是否是二叉搜索树，那我们可以使用中序递归遍历。只要之前的节点是二叉树搜索树，那么如果当前的节点小于上一个节点值那么就可以向下判断。只不过在过程中我们要求反退出。比如一个链表1->2->3->4，只要for循环遍历如果中间有不是递增的直接返回false即可。

if(root.val < pre)
    return false;

具体做法：

• step 1：首先递归到最左，初始化maxLeft与pre。
• step 2：然后往后遍历整棵树，依次连接pre与当前节点，并更新pre。
• step 3：左子树如果不是二叉搜索树返回false。
• step 4：判断当前节点是不是小于前置节点，更新前置节点。
• step 5：最后由右子树的后面节点决定。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    int pre = Integer.MIN_VALUE;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // write code here
        //中序遍历
        if(root ==  null) return true;
        //先进入左子树
        if(!isValidBST(root.left)){
            return false;
        }
        if(root.val<pre){
            return false;
        }
        //更新最值
        pre = root.val;
        //在进入右子树
        return isValidBST(root.right);
        
    }
}

BM35 判断是不是完全二叉树

思路：

对完全二叉树最重要的定义就是叶子节点只能出现在最下层和次下层，所以我们想到可以使用队列辅助进行层次遍历——从上到下遍历所有层，每层从左到右，只有次下层和最下层才有叶子节点，其他层出现叶子节点就意味着不是完全二叉树。

具体做法：

• step 1：先判断空树一定是完全二叉树。
• step 2：初始化一个队列辅助层次遍历，将根节点加入。
• step 3：逐渐从队列中弹出元素访问节点，如果遇到某个节点为空，进行标记，代表到了完全二叉树的最下层，若是后续还有访问，则说明提前出现了叶子节点，不符合完全二叉树的性质。
• step 4：否则，继续加入左右子节点进入队列排队，等待访问。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PlMO085A-1679386637750)(C:\Users\jquery\Desktop\国密算法\八股文\assets\07986E476EB2CECD3C5F81D0BCADBE12.gif)]

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        //左右都为null
        
        //空树一定为完全二叉树
        if(root == null) return true;
        //辅助队列
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        //定义一个首次出现的标记位
        boolean notComplete = false;
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            if(cur == null){
                //标记第一次遇到空节点
                notComplete = true;
                continue;
            }
            //后续访问以及已经遇到空节点了，说明经过了叶子
            if(notComplete) return false;
            q.add(cur.left);
            q.add(cur.right);
        }
        return true;
    }
}

BM36 判断是不是平衡二叉树

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        //空树为平衡树
        if (root == null) return true;
        int left = deep(root.left);
        int right = deep(root.right);
        //左子树深度减去右子树相差绝对值大于1
        if (left - right > 1 || left - right < -1) {
            return false;
        }
        //同时左右子树还必须是平衡的
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }

    private int deep(TreeNode root) {
        //空节点深度为0
        if (root == null) return 0;

        //递归计算左右子树的深度
        int left = deep(root.left);
        int right = deep(root.right);

        //子树最大深度加上自己
        return (left > right) ? left + 1 : right + 1;
    }
}

BM37 二叉搜索树的最近公共祖先

思路：

二叉搜索树没有相同值的节点，因此分别从根节点往下利用二叉搜索树较大的数在右子树，较小的数在左子树，可以轻松找到p、q：

//节点值都不同，可以直接用值比较
while(node.val != target) { 
    path.add(node.val);
    //小的在左子树
    if(target < node.val) 
        node = node.left;
    //大的在右子树
    else 
        node = node.right;
}

直接得到从根节点到两个目标节点的路径，这样我们利用路径比较就可以找到最近公共祖先。

具体做法：

• step 1：根据二叉搜索树的性质，从根节点开始查找目标节点，当前节点比目标小则进入右子树，当前节点比目标大则进入左子树，直到找到目标节点。这个过程成用数组记录遇到的元素。
• step 2：分别在搜索二叉树中找到p和q两个点，并记录各自的路径为数组。
• step 3：同时遍历两个数组，比较元素值，最后一个相等的元素就是最近的公共祖先。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        //求根节点到两个节点的路径
        ArrayList<Integer> path_p = getPasth(root, p);
        ArrayList<Integer> path_q = getPasth(root, q);

        int res = 0;
        //比较元素值，最后一个相等的元素就是最近的公共祖先。
        for (int i = 0; i < path_p.size() && i < path_q.size(); i++) {
            int x = path_p.get(i);
            int y = path_q.get(i);
            //最后一个相同的节点就是最近公共祖先
            if (x == y) {
                res = path_p.get(i);
            } else {
                break;
            }

        }
        return res;
    }

    //求得根节点到目标节点的路径
    public ArrayList<Integer> getPasth(TreeNode root, int target) {
        ArrayList<Integer> path = new ArrayList<Integer>();
        TreeNode node = root;
        //节点值都不同，可以直接比较
        while (node.val != target) {
            path.add(node.val);
            //小的在左子树
            if (target < node.val) {
                node = node.left;
            } else {
                //大的在右子树
                node = node.right;
            }

        }
        path.add(node.val);
        return path;
    }
}

BM38 在二叉树中找到两个节点的最近公共祖先

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        ArrayList<Integer> path1 = new ArrayList<>();
        ArrayList<Integer> path2 = new ArrayList<>();
        //求根节点到两个节点的路径
        dfs(root,path1,o1);
        //重置
        flag = false;
        dfs(root,path2,o2);
        int res=0;
        //比较两个路径，找到第一个不同的点
        for(int i=0;i<path1.size()&&i<path2.size();i++){
            int x = path1.get(i);
            int y = path2.get(i);
            if(x==y){
                //最后一个相同的节点就是最近公共祖先
                res = x;
            }else{
                break;
            }
        }
        return res;
    }
    //记录是否找到到o的路径
    public boolean flag = false;
    //求得根节点到目标节点的路径
    public void dfs(TreeNode root, ArrayList<Integer> path, int o) {
        if (flag || root == null) {
            return;
        }
        path.add(root.val);
        //节点不同值都不同，可以直接用值比较
        if (root.val == o) {
            flag = true;
            return;
        }
        //dfs 遍历查找
        dfs(root.left, path, o);
        dfs(root.right, path, o);
        if (flag) return;
        path.remove(path.size() - 1);
    }
}

BM39 序列化二叉树

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/

import java.util.*;

public class Solution {
    String SEP = ",";
    String NULL = "#";
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }
    //辅助函数，将二叉树存入StringBuilder中
    void serialize(TreeNode root, StringBuilder sb) {
        if(root == null){
            sb.append(NULL).append(SEP);
            return;
        }
        //前序遍历位置
        sb.append(root.val).append(SEP);

        serialize(root.left,sb);
        serialize(root.right,sb);
    }

    TreeNode Deserialize(String str) {
        //将字符串转成列表
        LinkedList<String> nodes = new LinkedList<>();
        for(String s:str.split(SEP)){
            nodes.addLast(s);
        }
        return deserialize(nodes);

    }

    TreeNode deserialize( LinkedList<String> nodes){
        if(nodes.isEmpty()) return null;
        //前序遍历位置,列表最左侧就是和根节点
        String first = nodes.removeFirst();
        if(first.equals(NULL)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left = deserialize(nodes);
        root.right =deserialize(nodes);

        return root;
    }
}

BM40 重建二叉树

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
        int n = pre.length;
        int m = vin.length;
        //每个遍历都不能为0
        if (n == 0 || m == 0) {
            return null;
        }
        //构建根节点 根节点必定在pre中选
        TreeNode root = new TreeNode(pre[0]);
        for (int i = 0; i < n; i++) {
            //找到中序遍历中的前序第一个元素,依据它划分左右子树
            if (pre[0] == vin[i]) {
                //构建左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));
                //构建右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(vin,i+1,vin.length));
                break;
            }
        }
        return root;
    }
}

BM41 输出二叉树的右视图

思路：

首先根据前序遍历和中序遍历生成二叉树

然后使用层序遍历得到每一层的一个数组

针对每一层的数组，取最后一个数，即可完成

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */

    public int[] solve (int[] xianxu, int[] zhongxu) {
        TreeNode root = reConstructBinaryTree(xianxu, zhongxu);
        ArrayList<ArrayList<Integer>> res = getLevelList(root);
        ArrayList<Integer> list = new ArrayList<>();
        //将二叉树 层次便利的 每层的额最后一个 值存入新的 ArrayList 中 转化为 数组
        for (int i = 0; i < res.size(); i++) {
            list.add(res.get(i).get(res.get(i).size() - 1));
        }
        // int arr[] = new int[list.size()];
        // for (int i = 0; i < list.size(); i++) {
        //     arr[i] = list.get(i);
        // }
        int arr[] = list.stream().mapToInt(Integer::valueOf).toArray();
        return arr;
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        int n = pre.length;
        int m = vin.length;
        //每个遍历都不能为0
        if (n == 0 || m == 0) return null;

        //构建根节点，根节点必定在pre中选\
        TreeNode root = new TreeNode(pre[0]);
        for (int i = 0; i < n; i++) {
            //找到中序遍历中的前序第一个元素，依据它划分左右子树
            if (pre[0] == vin[i]) {
                //构建左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1),
                                                  Arrays.copyOfRange(vin, 0, i));
                //构建右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
                                                   Arrays.copyOfRange(vin, i + 1, vin.length));
                break;
            }
        }
        return root;
    }

    //此方法用来 二叉树的 层次遍历到 ArrayList<ArrayList<Integer>>中
    private  ArrayList<ArrayList<Integer>> getLevelList(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            ArrayList<Integer> row = new ArrayList<>();
            int n = q.size();
            for (int i = 0; i < n; i++) {
                TreeNode cur = q.poll();
                row.add(cur.val);
                if (cur.left != null) q.add(cur.left); //是cur，不是root
                if (cur.right != null) q.add(cur.right);//是cur，不是root
            }
            result.add(row);
        }
        return result;
    }

    
}