class Node {
int value; // 樹(shù)中存儲(chǔ)的數(shù)據(jù)
Node firstChild; // 第一個(gè)孩子引用
Node nextBrother; // 下一個(gè)兄弟引用
}

// 孩子表示法
class Node {
int val; // 數(shù)據(jù)域
Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹(shù)
Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹(shù)
}

// 孩子雙親表示法
class Node {
int val; // 數(shù)據(jù)域
Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹(shù)
Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹(shù)
Node parent; // 當(dāng)前節(jié)點(diǎn)的根節(jié)點(diǎn)
}

class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val){
        this.val = val;
    }
 }
public class BinaryTree {
	//創(chuàng)建一個(gè)二叉樹(shù)
    public TreeNode createTree(){
        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.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        return A;
    }

 void preOrderTraversal(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

 public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
        binaryTree.preOrderTraversal(root);//前序遍歷
        }

 // 中序遍歷
    void inOrderTraversal(TreeNode root){
        if(root == null){
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val + " ");
        inOrderTraversal(root.right);
    }

public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
         binaryTree.inOrderTraversal(root);//中序遍歷
        }

// 后序遍歷
    void postOrderTraversal(TreeNode root){
        if(root == null){
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val + " ");
    }

public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
        binaryTree.postOrderTraversal(root);//后序遍歷
        }

 static int size = 0;//靜態(tài)變量
    void getSize1(TreeNode root){
        if(root == null){
            return;
        }
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

int getSize2(TreeNode root){
        if(root == null){
            return 0;
        }
        return  getSize2(root.left) + getSize2(root.right)+1;
    }

 public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
        binaryTree.getSize1(root);
        System.out.println(BinaryTree.size);
        System.out.println("============");
        System.out.println(binaryTree.getSize2(root));
   }

//遍歷這顆二叉樹(shù)，只要節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都是空的，那么就是葉子
    static int leafSize = 0;
    void getLeafSize1(TreeNode root){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            leafSize++;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

//整棵樹(shù)的葉子結(jié)點(diǎn) = 左子樹(shù)葉子 + 右子樹(shù)葉子
    int getLeafSize2(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return  getLeafSize2(root.left) + getLeafSize2(root.right);
    }

public class test01 {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
        binaryTree.getLeafSize1(root);
        System.out.println(BinaryTree.leafSize);//遍歷思路-求葉子結(jié)點(diǎn)個(gè)數(shù)
        System.out.println("+++++++++++++");
        //binaryTree.getLeafSize2(root);
        //System.out.println(BinaryTree.leafSize);//子問(wèn)題思路-求葉子結(jié)點(diǎn)個(gè)數(shù)
        System.out.println(binaryTree.getLeafSize2(root));
  }

// 子問(wèn)題思路-求第 k 層結(jié)點(diǎn)個(gè)數(shù)
    int getKLevelSize(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
   return getKLevelSize(root.left,k-1) + getKLevelSize(root.right,k - 1);
    }

public class test01 {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
 		System.out.println(binaryTree.getKLevelSize(root,3));
 }

int getHeight(TreeNode root){
        if(root == null){
            return  0;
        }
        int leftTree = getHeight(root.left);
        int rightTree = getHeight(root.right);
        return ((leftTree > rightTree) ? leftTree + 1 : rightTree + 1);
    }

public class test01 {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
 		int hight = binaryTree.getHeight(root);
        System.out.println(hight);
 }

    TreeNode find(TreeNode root, char val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
       TreeNode ret = find(root.left,val);
        if(ret != null){
            return ret;
        }
        ret = find(root.right,val );
        if(ret != null){
            return ret;
        }
        return null;
    }

public class test01 {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
 		//查找樹(shù)中得指定val值
       TreeNode ret = binaryTree.find(root,'f');//如果沒(méi)有找到則顯示空指針異常
        System.out.println(ret.val);
 }

 // 層序遍歷
    void levelOrderTraversal(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
           TreeNode top = queue.poll();
            System.out.print(top.val+" ");
            if(top.left != null){
                queue.offer(top.left);
            }
            if (top.right != null){
                queue.offer(top.right);
            }
        }
        System.out.println();
    }

public class test01 {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
 		binaryTree.levelOrderTraversal(root);//層序遍歷
 }

// 判斷一棵樹(shù)是不是完全二叉樹(shù)
    boolean isCompleteTree(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode top = queue.poll();//彈出一個(gè)元素
            if(top != null){
                queue.offer(top.left);
                queue.offer(top.right);
            }else{
                break;
            }
        }
        while (!queue.isEmpty()){
            TreeNode cur = queue.peek();
            if (cur == null){
                queue.poll();
            }else {
                //說(shuō)明不是完全二叉樹(shù)
                return false;
            }
        }
        return true;
    }

public class test01 {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
        //判斷一棵樹(shù)是不是完全二叉樹(shù)
 		System.out.println(binaryTree.isCompleteTree(root)); 
 }

 //非遞歸實(shí)現(xiàn)
    // 前序遍歷
    void preOrderTraversalNor(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

 // 中序遍歷
    void inOrderTraversalNor(TreeNode root){
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.empty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }

    }

// 后序遍歷非遞歸
    void postOrderTraversalNor(TreeNode root){
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;//用來(lái)指定上一個(gè)被打印過(guò)的元素
        while (cur != null || !stack.empty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            if(cur.right == null || cur.right == pre ){
                TreeNode popNode = stack.pop();
                System.out.print(popNode.val + " ");
                pre = cur;
                cur = null;
            }else {
                cur = cur.right;
            }
        }
    }

 public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
       // binaryTree.preOrderTraversal(root);//前序遍歷
        //System.out.println();
        binaryTree.preOrderTraversalNor(root);//前序遍歷非遞歸
        System.out.println();
        //binaryTree.postOrderTraversal(root);//后序遍歷
        //System.out.println();
        binaryTree.postOrderTraversalNor(root);//后序遍歷非遞歸
        System.out.println();
        //binaryTree.inOrderTraversal(root);//中序遍歷
        //System.out.println();
        binaryTree.inOrderTraversalNor(root);//中序遍歷非遞歸
        System.out.println();
}