出处：代码随想录 代码随想录 代码随想录代码随想录
二叉搜索树
有序，若左子树不为空，则左子树上所有节点的值都小于根节点的值。
若右子树不为空，则右子树上所有节点的值都小于根节点的值。
左右子树分别为二叉搜索树。
用数组来存储二叉树如何遍历的呢？
如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
链式存储是大家很熟悉的一种方式，那么我们来看看如何顺序存储呢？
public class BinaryTree {/*** 前序遍历*/public List<Integer> preOrderTraverse(TreeNode root) {List<Integer> result = new ArrayList<>();preOrder(root, result);return result;}private void preOrder(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preOrder(root.left, result);preOrder(root.right, result);}/*** 前序遍历的迭代方法* 前序遍历是中左右，每次先处理中间节点，所以先将根节点放入栈中，再将右子节点放入栈，再加入左子节点* 这样弹出的时候是中左右*/public List<Integer> preOrderIter(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val);if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}return result;}/*** 中序遍历*/public List<Integer> inOrderTraverse(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}private void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val);inorder(root.right, list);}/*** 中序遍历的迭代写法* 中序遍历是左中右，先访问的是二叉树顶部的节点，* 然后一层一层向下访问，直到到达树左面的最底部，* 再开始处理节点（也就是在把节点的数值放进result数组中），* 这就造成了处理顺序和访问顺序是不一致的。** 在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。* 遍历顺序：左中右，入栈顺序：左 右*/public List<Integer> inOrderIter(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> stack = new Stack<>();// 用指针来遍历帮助访问节点TreeNode cur = root;while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.push(cur);cur = cur.left;} else {cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}/*** 后序遍历*/public List<Integer> postOrderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root, res);return res;}private void postorder(TreeNode root, List<Integer> list) {if (root == null) {return;}postorder(root.left, list);postorder(root.right, list);list.add(root.val);}/*** 后序遍历* 先序遍历是中左右，后续是左右中，就把前序的reverse一下*/public List<Integer> postOrderTraverse(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val);if (node.left != null) {stack.push(node.left);}if (node.right != null) {stack.push(node.right);}}Collections.reverse(result);return result;}/*** 二叉树的层序遍历* 需要辅助的队列来实现，队列先进先出，符合一层一层遍历的逻辑，*//*** 层序遍历的递归方式*/public List<List<Integer>> levelOrderDfs(TreeNode root) {List<List<Integer>> resList = new ArrayList<List<Integer>>();levelOrderDfsHelper(root, 0, resList);return resList;}private void levelOrderDfsHelper(TreeNode node, int deep, List<List<Integer>> resList) {if (node == null) {return;}deep++;if (resList.size() < deep) {// 层级增加时，list的Item也增加，利用list的索引值进行层级界定List<Integer> item = new ArrayList<>();resList.add(item);}resList.get(deep - 1).add(node.val);levelOrderDfsHelper(node.left, deep, resList);levelOrderDfsHelper(node.right, deep, resList);}/*** 层序遍历的BFS方式*/public List<List<Integer>> levelOrderBfs(TreeNode root) {List<List<Integer>> resList = new ArrayList<List<Integer>>();levelOrderBfsHelper(root, resList);return resList;}private void levelOrderBfsHelper(TreeNode node, List<List<Integer>> resList) {if (node == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(node);while (!queue.isEmpty()) {List<Integer> itemList = new ArrayList<>();int len = queue.size();while (len > 0) {TreeNode treeNode = queue.poll();itemList.add(treeNode.val);if (treeNode.left != null) {queue.offer(treeNode.left);}if (treeNode.right != null) {queue.offer(treeNode.right);}len--;}resList.add(itemList);}}/*** 翻转二叉树* 44*/\ /\* 2 7 -> 7 2* /\ /\ /\ /\* 1 3 6 9 9 6 3 1** 翻转，将每个节点的左右孩子相互交换一下* 用什么遍历顺序呢？* 使用前序和后序都是可以的，但是中序很不方便，因为中序会把某些节点的左右孩子翻转两次* 层序遍历也可以，只要能把每个节点的左右孩子翻转一下的遍历方式都可以*//*** 递归方法*/public TreeNode invertTreeBacktracking(TreeNode root) {if (root == null) {return null;}invertTreeBacktracking(root.left);invertTreeBacktracking(root.right);swapChildren(root);return root;}private void swapChildren(TreeNode root) {TreeNode temp = root.left;root.left = root.right;root.right = temp;}/*** 使用BFS*/public TreeNode invertTreeBfs(TreeNode root) {if (root == null) {return null;}ArrayDeque<TreeNode> deque = new ArrayDeque<>();deque.offer(root);while (!deque.isEmpty()) {int size = deque.size();while (size-- > 0) {TreeNode node = deque.poll();swapChildren(node);if (node.left != null) {deque.offer(node.right);}if (node.right != null) {deque.offer(node.left);}}}return root;}}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}
leetcode题：
/*** LCP 10. 二叉树任务调度***/public double minimalExecTime(TreeNode root) {if (root == null) {return 0;}return dfsHelper(root)[1];}private double[] dfsHelper(TreeNode node) {if (node == null) {return new double[]{0, 0};}// 递归左右子树double[] resRight = dfsHelper(node.right);double[] resLeft = dfsHelper(node.left);//return 这一层的结果return new double[]{resLeft[0] + resRight[0] + node.val,node.val + Math.max(Math.max(resLeft[1], resRight[1]),(resLeft[0] + resRight[0]) / 2.0)};}
