树代码

未分类

完全二叉树

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
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flag = false;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            // 有右孩子没有左孩子
            if(node.right != null && node.left == null) return false;
            // 遇到了左右孩子不双全的节点后，遇到了非叶子节点
            if(flag && (node.left != null || node.right != null)) return false;
            // 遇到左右孩子不双全的节点
            if((node.left != null && node.right == null) || (node.left == null && node.right == null)) flag = true;
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        return true;
    }
}

前序中序重建二叉树

//递归的思想是把一个大问题分成层层向下的小问题 每一层解决问题的方法都是一样的 我们考虑的就是本层的解决问题逻辑和结束条件
//第一层 [1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
//第二层(1左子树) [2,4,7],[4,7,2] 每层解决问题的方法都是一样的
//第三层(2左子树) [4,7],[4,7]
//第三层(4右子树) [7],[7]
//每层子树都是一样的解决方式
//ps:先序+中序 中序+后序 都可以确定一棵树 先序+后序不行
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
        int m = pre.length;
        int n = vin.length;
        //中序遍历数组和先序遍历数组长度都不能为空
        if (m == 0 ||
                n == 0) { //换成&&也一样对 其实这道题里只要它中序遍历为0了 也就不可能有先序遍历的
            return null;
        }
        //计算器a a代表节点node的左子树有多少节点
        int a = 0;
        //这层子树的根节点必为先序遍历数组第一个位置的节点
        TreeNode treeNode = new TreeNode(pre[0]);
        for (int i = 0; i < vin.length; i++) {
            if (vin[i] != treeNode.val) {
                a++;
            } else {
                //node节点的左子树就是中序遍历node左边的那部分，同时把这左子树这部分的先序遍历数组传进去
                treeNode.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, 1 + a),
                                                      Arrays.copyOfRange(vin, 0, a));
                //node节点的右子树就是中序遍历node右边的那部分，同时把这右子树这部分的先序遍历数组传进去
                treeNode.right = reConstructBinaryTree(Arrays.copyOfRange(pre, 1 + a,
                                                       pre.length), Arrays.copyOfRange(vin, 1 + a, vin.length));
            }
        }
        //返回这层子树的根节点
        return treeNode;
    }
}