文章目录

• • • • • 114. 二叉树展开为链表
        • 106. 从中序与后序遍历序列构造二叉树
        • 96. 不同的二叉搜索树
        • 863. 二叉树中所有距离为 K 的结点
        • 剑指 Offer 27. 二叉树的镜像
        • 257. 二叉树的所有路径
        • 108. 将有序数组转换为二叉搜索树
        • 617. 合并二叉树
        • 剑指 Offer 07. 重建二叉树
        • 99. 恢复二叉搜索树

114. 二叉树展开为链表

class Solution {public void flatten(TreeNode root) {while (root!=null){// 重复处理TreeNode pNode = root.left;if(pNode != null){// 找到root节点左子树的右子树的最右侧节点while (pNode.right!=null){pNode = pNode.right;}// pNode的右子节点指向root的右子节点pNode.right = root.right;// root的右子节点执行root的左子节点root.right = root.left;// root的左子节点置为nullroot.left = null;}root = root.right;}}
}

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

class Solution {HashMap map = new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {int inleft = 0;int inrignt = inorder.length-1;int postleft = 0;int postright = postorder.length-1;for (int i=0;imap.put(inorder[i],i);}return rebuild(inleft,inrignt,postleft,postright,postorder,inorder);}private TreeNode rebuild(int inleft, int inrignt,  int postleft, int postright, int[] postorder, int[] inorder) {if(inleft>inrignt || postleft>postright){return null;}int rootValue = postorder[postright];TreeNode root = new TreeNode(rootValue);int index = map.get(rootValue);root.left = rebuild(inleft,index-1,postleft,postleft+index-inleft-1,postorder,inorder);root.right = rebuild(index+1,inrignt,postleft+index-inleft,postright-1,postorder,inorder);return root;}
}

96. 不同的二叉搜索树

class Solution {public int numTrees(int n) {// G(n) = G(0)*G(n-1) + G(1)*G(n-2) + ... +G(n-1)*G(0)// 动态规划int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){// G(n) = G(0)*G(n-1) + G(1)*G(n-2) + ... + G(n-1)*G(0)//dp[2] = dp[0]*dp[1] +  dp[1]*dp[0]dp[i] += dp[j-1]*dp[i-j];}}return dp[n];}
}

863. 二叉树中所有距离为 K 的结点

class Solution {Map map = new HashMap<>();List res = new ArrayList<>();public List distanceK(TreeNode root, TreeNode target, int k) {// 从root出发dfs记录每个节点的父节点findParant(root);// 从target出发dfs寻找所有深度为k的节点TreeNode from = null;int depth = 0;findRes(target,from,depth,k);return res;}private void findRes(TreeNode node, TreeNode from, int depth, int k) {if(node==null){return;}if(depth==k){res.add(node.val);return;}if(node.left!=from){findRes(node.left,node,depth+1,k);}if(node.right!=from){findRes(node.right,node,depth+1,k);}if(map.get(node.val) != from){findRes(map.get(node.val),node,depth+1,k);}}private void findParant(TreeNode node) {if(node.left!=null){map.put(node.left.val,node);findParant(node.left);}if(node.right!=null){map.put(node.right.val,node);findParant(node.right);}}
}

剑指 Offer 27. 二叉树的镜像

class Solution {public TreeNode mirrorTree(TreeNode root) {if(root==null){return null;}TreeNode temp = root.left;root.left = root.right;root.right = temp;mirrorTree(root.left);mirrorTree(root.right);return root;}
}

257. 二叉树的所有路径

方法1：

class Solution {public List binaryTreePaths(TreeNode root) {List res = new ArrayList<>();dfs(root,"",res);return res;}private void dfs(TreeNode root, String path, List res) {if(root==null){return;}// 到达根节点，将路径添加到resif(root.left==null && root.right==null){res.add(path+root.val);return;}// 不是叶子节点，分别遍历左右节点dfs(root.left,path+root.val+"->",res);dfs(root.right,path+root.val+"->",res);}
}

方法2：

class Solution {public List binaryTreePaths(TreeNode root) {List res = new ArrayList<>();Stack