【牛客网刷题记录】【java】二叉树

（1）二叉树的前中后遍历

最基本的树的遍历，不会可以重开了

public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @return int整型一维数组*/public void preorder(List<Integer> list, TreeNode root){// 先序遍历则先处理根节点list.add(root.val);if(root.left!=null){preorder(list, root.left);}if(root.right!=null){preorder(list, root.right);}}public int[] preorderTraversal (TreeNode root) {if(root==null){return new int[0];}// write code hereList<Integer> tmp=new ArrayList<>();preorder(tmp, root);int [] res=new int[tmp.size()];for(int i=0; i<res.length; i++){res[i]=tmp.get(i);}return res;}
}

前序遍历的顺序为 根-左-右，中序为左-根-右，后序为左-右-根，因此这些遍历也可以说是先根、中根、后根遍历。

 public void preorder(List<Integer> list, TreeNode root){// 先序遍历则先处理根节点// list.add(root.val);if(root.left!=null){preorder(list, root.left);}//list.add(root.val); 中序遍历if(root.right!=null){preorder(list, root.right);}//list.add(root.val); 后续遍历}

(2) 二叉树的最大深度

链接
不知道空间复杂度为O(1)的算法是什么…除非你修改树的数据结构，因此这显然是不成立的。
首先可以用dfs来做，空间复杂度为O(n),即为栈的高度。空间复杂度会为n是因为树可能只有一个分支。我们可以再写一个函数来完成dfs。即如果左子非空，则向左dfs，同时deep+1.右子非空，则向右dfs，同时deep+1. 最后查看max与deep的大小，并且更改max。如果理解不了可以学习栈的知识，以及递归是怎么做到的。

int max=0;public void dfs(TreeNode root, int deep){if(root.left!=null){dfs(root.left, deep+1);}if(root.right!=null){dfs(root.right, deep+1);}if(max<deep){max=deep;} }public int maxDepth (TreeNode root) {// write code hereif(root==null){return 0;}dfs(root,1);return max;}

除此之外，还可以用层序遍历，即记录有多少层，这样也可以得到最大深度。但空间复杂度一定不为O(1)，而是O(n).
层序遍历需要单独记录一下每一层的元素，这样可以判断何时遍历完一层。

public int maxDepth (TreeNode root) {if(root==null){return 0;}int max=0;// write code hereQueue<TreeNode> q=new LinkedList<>();q.add(root);while(!q.isEmpty()){int len=q.size();for(int i=0; i<len; i++){TreeNode t=q.poll();if(t.left!=null){q.add(t.left);}if(t.right!=null){q.add(t.right);}}max++;}return max;}

（3） 二叉搜索树与双向链表

链接
不难发现，二叉搜索树的中序遍历就是我们最终需要的顺序，因此这题一定会和中序遍历扯上关系。我们的基本思路就是中序遍历，即：

 public void inorder(List<Integer> list, TreeNode root){if(root.left!=null){preorder(list, root.left);}list.add(root.val); // 或者其他操作 if(root.right!=null){preorder(list, root.right);}}

重点问题是如何处理前驱和后继的指向。可以创建空节点pre，前驱用当前节点的左指针指向pre，而pre的右指针指向当前节点，最后将pre指向当前节点。我们的这部分就是中序遍历的操作部分，即上面代码的 其他操作。
我们的convert操作即为inorder遍历，但不需要做任何操作。中序的节点操作即对我刚刚描述的内容的转义。

public class Solution {TreeNode pre=null, head=null;public TreeNode Convert(TreeNode pRootOfTree) {if(pRootOfTree==null){return null;}Convert(pRootOfTree.left);// 开始找到头节点if(head==null){head=pRootOfTree;pre=head;}else{pRootOfTree.left=pre;pre.right=pRootOfTree;pre=pRootOfTree;}Convert(pRootOfTree.right);return head;}
}

(4) 合并二叉树

链接
可以用递归来做，如果t1为null则返回t2，反之返回t1。每次都合并一次节点即可。

public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {if(t1==null){return t2;}if(t2==null){return t1;}// write code hereTreeNode head=new TreeNode(t1.val+t2.val);head.left=mergeTrees(t1.left, t2.left);head.right=mergeTrees(t1.right, t2.right);return head;}