BinaryTree树

1.“递归”是树中重要的思想；

2.度：一个节点的子节点数

3.

4完全二叉树：除最后一行，为满二叉树；（节点数为偶，n1=0,节点数为奇，n1=1）；

5.节点数=边数+1，2*边数=总度数；

package BinaryTree;

import com.sun.source.tree.Tree;

import java.sql.SQLOutput;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: czt20
 * Date: 2026 -01-08
 * Time: 17:13
 */
class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    TreeNode creatTree() {
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');
        a.right = c;
        a.left = b;
        b.right = e;
        b.left = d;
        e.right = h;
        c.left = f;
        c.right = g;
        return a;
    }

    //前序遍历
    void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //前序遍历(非递归)
    public void preOrderNor(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur =root;
        stack.push(root);
        while (!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.println(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }
    //中序遍历
    void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //中序遍历(非递归)
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> res=new LinkedList<>();
        inorderTraversalNor(root,res);
        return res;
    }
    public void inorderTraversalNor(TreeNode root,List<Character> res) {
        if (root == null) return;
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur =root;
        while (!stack.isEmpty()||cur!=null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            res.add(top.val);
            cur = top.right;
        }
    }
    //后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //层序遍历
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> sr = new LinkedList<>();
        sr.offer(root);

        while (!sr.isEmpty()){
            TreeNode ree=sr.poll();
            System.out.print(ree.val+" ");
            if (ree.left!=null)sr.offer(ree.left);
            if (ree.right!=null)sr.offer(ree.right);
        }
     
    }
    List<List<Integer>> lee= new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder2(TreeNode root) {
        if(root==null)return lee;
        levelOrder2(root,0);
        return lee;
    }
    public void levelOrder2(TreeNode root,int val){
        if(lee.size()==val){
            lee.add(new ArrayList<Integer>());
        }
        lee.get(val).add(root.val);
        if(root.left!=null)levelOrder2(root.left,val+1);
        if(root.right!=null)levelOrder2(root.right,val+1);
        return;
    }
    //判断是否为完全二叉树
    public boolean ifwanquan(TreeNode root){
        if (root == null) {
            return true;
        }
        Queue<TreeNode> sr = new LinkedList<>();
        sr.offer(root);

        while (!sr.isEmpty()){
            TreeNode ree=sr.poll();
            if (ree!=null){
                sr.offer(ree.left);
                sr.offer(ree.right);
            }else{
             break;
            }
        }
         while(!sr.isEmpty()){
             TreeNode lee = sr.poll();
             if (lee!=null){
                 return  false;
             }
         }
         return true;
    }
    //获取树中节点的个数
    static int count = 0;

    void size(TreeNode root) {
        if (root == null) {
            return;
        }
        count++;
        size(root.left);
        size(root.right);
    }

    //方法2：左树加右数；
    int size2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return size2(root.right) + size2(root.left) + 1;
    }

    //叶子的个数(同理)
    int leaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return leaves(root.left) + leaves(root.right);
    }

    //查找第k层右多少节点
    int getKlevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }

        return getKlevelNodeCount(root.left, k - 1) + getKlevelNodeCount(root.right, k - 1);
    }

    //树的高度
    int getHight(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return Math.max(getHight(root.right), getHight(root.left)) + 1;
    }

    TreeNode findval(TreeNode root, char val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        TreeNode le = findval(root.left, val);
        if (le != null) {
            return le;
        }
        TreeNode ri = findval(root.right, val);
        if (ri != null) {
            return ri;
        }
        return null;
    }
}