算法：树

树的最大路径和

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
思路&＃xff1a;
递归&＃43;遍历

最大路径和

按照一个树 比如【a,b,c】 实际是三选一问题&＃xff1a;b&＃43;root 与c&＃43;root 或者 b&＃43;c&＃43;root
maxSum 用于更新最大和&＃xff0c;treeMaxSum

int maxSum&＃61; Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {treeMaxSum(root);return maxSum;}public int treeMaxSum(TreeNode root){if (root&＃61;&＃61;null) return 0;int left&＃61;Math.max(0,treeMaxSum(root.left));int right&＃61;Math.max(0,treeMaxSum(root.right));int tempMax&＃61;Math.max(left,right);tempMax&＃61;Math.max(tempMax,left&＃43;right);maxSum&＃61; Math.max(maxSum,tempMax&＃43;root.val);return Math.max(left,right)&＃43;root.val;}


根据前序 中序遍历结果还原二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

思路&＃xff1a;
遍历 &＃43; 递归

前序&＃xff1a;根左右
中序&＃xff1a;左根右
根据中序遍历 可以分出左子树与右子树&＃xff0c; 记录根的下标记 rootIndex&＃xff0c;左子树个数为rootIndex 前的个数leftNum&＃xff0c;从而知道前序遍历中的start&＃43;leftNum&＃43;1开始是左子树&＃xff0c;后面的全部是右子树。递归调用

public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTree(preorder, 0, preorder.length , inorder, 0, inorder.length );}public TreeNode buildTree(int[] preorder, int p_start, int p_end,int[] inorder, int i_start, int i_end) {if (p_start &＃61;&＃61; p_end) {return null;}TreeNode treeNode &＃61; new TreeNode(preorder[p_start]);int rootIndex &＃61; 0;for (int i &＃61; i_start; i < i_end; i&＃43;&＃43;) {if (inorder[i] &＃61;&＃61; preorder[p_start]) {rootIndex &＃61; i;}}int leftNum &＃61; rootIndex - i_start;treeNode.left &＃61; buildTree(preorder, p_start&＃43;1, p_start &＃43;1&＃43; leftNum , inorder, i_start, rootIndex );treeNode.right &＃61; buildTree(preorder, p_start &＃43;1&＃43; leftNum, p_end, inorder, rootIndex &＃43; 1, i_end);return treeNode;}

树按层遍历&＃xff08;BFS&＃xff09;

规律&＃xff1a; 利用队列 &＃xff0c;看作图的遍历
扩展&＃xff1a; 可以求深度

public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list &＃61; new ArrayList<>();if (root&＃61;&＃61;null) return list;Deque<TreeNode> queue &＃61; new ArrayDeque<>();queue.add(root);while (!queue.isEmpty()) {int size &＃61; queue.size();List<Integer> levelResult &＃61; new ArrayList<>();for (int i &＃61; 0; i < size; i&＃43;&＃43;) {TreeNode cur &＃61; queue.poll();levelResult.add(cur.val);if (cur.left !&＃61; null) {queue.add(cur.left);}if (cur.right !&＃61; null) {queue.add(cur.right);}}list.add(levelResult);}return list;}


树按深度遍历

非递归&＃xff0c;利用栈实现

//深度优先遍历List<TreeNode> treeList ;public List<TreeNode> dfs(TreeNode root) {treeList &＃61; new ArrayList<>();if(root&＃61;&＃61;null) {return null;}Stack<TreeNode> myStack&＃61;new Stack<>();myStack.add(root);while(!myStack.isEmpty()) {TreeNode node&＃61;myStack.pop(); //弹出栈顶元素//System.out.print(node.value&＃43;" ");treeList.add(node);//向栈中先压入右子树&＃xff0c;在压入左子树。这样出栈时&＃xff0c;先出左子树再出右子树.也就是,先遍历左边&＃xff0c;后遍历右边if(node.right!&＃61;null) {myStack.push(node.right);}if(node.left!&＃61;null) {myStack.push(node.left);}}return treeList;}


递归

List<TreeNode> treeNodeList &＃61; new ArrayList<>();;public List<TreeNode> dfsRec(TreeNode root) {if (root &＃61;&＃61; null) {return null;}treeNodeList.add(root);//System.out.print(root.value&＃43;" ");dfsRec(root.left);dfsRec(root.right);return treeNodeList;}