6.5(Java)(二叉树)

1.我的代码：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class MyBinaryTree {static class TreeNode {public char val;public TreeNode left;//左孩子的引用public TreeNode right;//右孩子的引用public TreeNode(char val) {this.val = val;}}/*** 创建一棵二叉树 返回这棵树的根节点** @return*/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;c.left = f;c.right = g;d.left = null;d.right = null;e.left = null;e.right = h;f.left = null;f.right = null;g.left = null;g.right = null;h.left = null;h.right = null;return a;}// 前序遍历public void preOrder(TreeNode root) {if (root == null) {return;}System.out.print(root.val + " ");this.preOrder(root.left);this.preOrder(root.right);}// 中序遍历void inOrder(TreeNode root) {if (root == null) {return;}this.inOrder(root.left);System.out.print(root.val + " ");this.inOrder(root.right);}// 后序遍历void postOrder(TreeNode root) {if (root == null) {return;}this.postOrder(root.left);this.postOrder(root.right);System.out.print(root.val + " ");}public int nodeSize;/*** 获取树中节点的个数：遍历思路*/int size(TreeNode root) {if (root == null) {return 0;}this.nodeSize++;size(root.left);size(root.right);return this.nodeSize;}/*** 获取节点的个数：子问题的思路** @param root* @return*/int size2(TreeNode root) {if (root == null) {return 0;}return 1 + size2(root.left) + size2(root.right);}/*获取叶子节点的个数：遍历思路*/public int leafSize = 0;int getLeafNodeCount1(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {this.leafSize++;return 1;}getLeafNodeCount1(root.left);getLeafNodeCount1(root.right);return this.leafSize;}/*获取叶子节点的个数：子问题*/int getLeafNodeCount2(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}return getLeafNodeCount2(root.left) + getLeafNodeCount2(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);}/*获取二叉树的高度时间复杂度：O(N)*/int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}// 检测值为value的元素是否存在TreeNode find(TreeNode root, char val) {if (root == null) {return null;}if (root.val == val) {return root;}TreeNode leftNode = find(root.left, val);if (leftNode != null) {return leftNode;}TreeNode rightNode = find(root.right, val);if (rightNode != null) {return rightNode;}return null;}//层序遍历void levelOrder(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();}// 判断一棵树是不是完全二叉树boolean isCompleteTree(TreeNode root) {if (root == null) {return true;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode cur = queue.peek();if (cur != null) {queue.poll();queue.offer(cur.left);queue.offer(cur.right);} else {break;}}while (!queue.isEmpty()) {TreeNode tmp = queue.poll();if (tmp != null) {return false;}}return true;}//非递归后序遍历public void postorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}TreeNode tmp = stack.peek();if (tmp.right == null || prev == tmp.right) {System.out.print(tmp.val + " ");prev = tmp;stack.pop();} else {cur = tmp.right;}}return;}//非递归前序遍历public void preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);System.out.print(cur.val + " ");cur = cur.left;}cur = stack.pop();cur = cur.right;}return;}//非递归中序遍历public void inorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}TreeNode tmp = stack.pop();if (tmp != null) {System.out.print(tmp.val + " ");}cur = tmp.right;}return;}
}

public class Test {public static void main(String[] args) {MyBinaryTree myBinaryTree = new MyBinaryTree();MyBinaryTree.TreeNode root = myBinaryTree.createTree();myBinaryTree.preOrder(root);System.out.println();myBinaryTree.preorderTraversal(root);System.out.println();myBinaryTree.inOrder(root);System.out.println();myBinaryTree.inorderTraversal(root);System.out.println();myBinaryTree.postOrder(root);System.out.println();myBinaryTree.postorderTraversal(root);System.out.println();System.out.println(myBinaryTree.size(root));System.out.println(myBinaryTree.size2(root));System.out.println(myBinaryTree.getLeafNodeCount1(root));System.out.println(myBinaryTree.getLeafNodeCount2(root));System.out.println(myBinaryTree.getKLevelNodeCount(root, 1));System.out.println(myBinaryTree.getKLevelNodeCount(root, 2));System.out.println(myBinaryTree.getKLevelNodeCount(root, 3));System.out.println(myBinaryTree.getKLevelNodeCount(root, 4));System.out.println(myBinaryTree.getHeight(root));MyBinaryTree.TreeNode ret = myBinaryTree.find(root, 'H');if (ret != null) {System.out.println(ret.val);}myBinaryTree.levelOrder(root);System.out.println(myBinaryTree.isCompleteTree(root));}
}

2.答案代码：

public class BinaryTree {static class TreeNode {public char val;public TreeNode left;//左孩子的引用public TreeNode right;//右孩子的引用public TreeNode(char val) {this.val = val;}}/*** 创建一棵二叉树 返回这棵树的根节点* 暂且使用穷举的方式创建二叉树* @return*/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;C.left = F;C.right = G;//E.right = H;return A;}// 前序遍历public void preOrder(TreeNode root) {if (root == null) return;System.out.print(root.val + " ");preOrder(root.left);preOrder(root.right);}// 中序遍历void inOrder(TreeNode root) {if (root == null) return;inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}// 后序遍历void postOrder(TreeNode root) {if (root == null) return;postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");}public static int nodeSize;/*** 获取树中节点的个数：遍历思路*/void size(TreeNode root) {if (root == null) return;nodeSize++;size(root.left);size(root.right);}/*** 获取节点的个数：子问题的思路** @param root* @return*/int size2(TreeNode root) {if (root == null) return 0;return size2(root.left)+ size2(root.right) + 1;}/*获取叶子节点的个数：遍历思路*/public static int leafSize = 0;void getLeafNodeCount1(TreeNode root) {if (root == null) return;if (root.left == null && root.right == null) {leafSize++;}getLeafNodeCount1(root.left);getLeafNodeCount1(root.right);}/*获取叶子节点的个数：子问题*/int getLeafNodeCount2(TreeNode root) {if (root == null) return 0;if (root.left == null && root.right == null) {return 1;}return getLeafNodeCount2(root.left) + getLeafNodeCount2(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);}/*获取二叉树的高度时间复杂度：O(N)*/int getHeight(TreeNode root) {if (root == null) return 0;int leftH = getHeight(root.left);int rightH = getHeight(root.right);return leftH > rightH ? leftH + 1 : rightH + 1;}// 检测值为value的元素是否存在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;}//层序遍历void levelOrder(TreeNode root) {if (root == null) return;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode cur = queue.poll();System.out.print(cur.val + " ");if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}}}// 判断一棵树是不是完全二叉树boolean isCompleteTree(TreeNode root) {if (root == null) return false;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode cur = queue.poll();if (cur != null) {queue.offer(cur.left);queue.offer(cur.right);} else {break;}}//第2次遍历队列 判断队列当中 是否存在非空的元素while (!queue.isEmpty()) {TreeNode cur = queue.peek();if (cur == null) {queue.poll();} else {return false;}}return true;}
}

3.题目：

1.简单题目：参考以下博客：

4.6.1树（二叉树）（C语言）

2.中等题目：

102. 二叉树的层序遍历

 答案

107. 二叉树的层序遍历 II

 答案

236. 二叉树的最近公共祖先

 答案

105. 从前序与中序遍历序列构造二叉树

 答案

106. 从中序与后序遍历序列构造二叉树

 答案

606. 根据二叉树创建字符串

 答案

144. 二叉树的前序遍历（非递归）

 答案

94. 二叉树的中序遍历（非递归） 

 答案

145. 二叉树的后序遍历（非递归） 

 答案