本文共 8385 字，大约阅读时间需要 27 分钟。
题解记录，TOP面试题，树相关。
给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root,null,null); } private boolean isValidBST(TreeNode root,TreeNode min,TreeNode max){ if (root==null){ return true; } if (min!=null&&root.val<=min.val){ return false; } if (max!=null &&root.val>=max.val){ return false; } return isValidBST(root.left,min,root)&&isValidBST(root.right,root,max); } Public Class Solution{ public boolean isSmmetric (TreeNode root){ return isSmmetric(root,root);}private boolean isSmmetric(TreeNode root1,TreeNode root2){ if{ root1==null&&root2==null}{ return true;} if(root1==null||root2==null){ return false;} return (root1.val==root2.val)&&isSmmetric(root1.left,root2,right)&&isSmmetric(root1.right,root2.left); }} struct Node { int val; Node *left; Node *right; Node *next;} 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。 class Solution { public Node connect(Node root) { if(root==null){ return root; } connect(root.right,root.left); return root; } private void connect(Node r,Node l){ if (r==null||l==null){ return; } l.next=r; connect(r.right,r.left); connect(l.right,l.left); connect(r.left,l.right); }} 给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数Class Solution{ int max=0; public int maxDepth(TreeNode root){ dfs(root,0); return max;} private void dfs(TreeNode root ,int k){ if (root==null){ if (max 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）
Class Solution{ TreeNode ans; public TreeNode lowestAcestor(TreeNode root,TreeNode p,TreeNode q){ boolean l = isAncestor(root,p,q); return ans;} private boolean isAncestor(TreeNode root,TreeNode p,TreeNode q){ if (root==null){ return true;} boolean l = isAncestor(root.left,p,q); boolean r = isAncestor(root.right,p,q); if((l&&r)||((root.val==p.val||root.val==q.val)&&(l||r))){ ans = root; } return l||r||(root.val==p.val||root.val==q.val); } } 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
Class Solution{ int ans=0; int i=0; public int findKthMin(TreeNode root,int k){ mid(root,k); return ans; } public void mid(TreeNode root,int k){ if (root==null){ return; } mid(root.left,k); i=i+1; if (k==i){ ans=root.val; return; } mid(root.right,k); }} 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）
class Solution { public List > levelOrder(TreeNode root) { List > li =new ArrayList<>(); Queue q = new LinkedList<>(); if (root!=null){ q.offer(root); } while(!q.isEmpty()){ int N = q.size(); List que = new LinkedList<>(); for (int i =0;i
给定一个二叉树的根节点 root ，返回它的 中序遍历。
class Solution { public List inorderTraversal(TreeNode root) { List li= new ArrayList<>(); inorderTraversal(root,li); return li; } private void inorderTraversal(TreeNode root,List li){ if (root==null){ return; } if(root.left!=null){ inorderTraversal(root.left,li); } li.add(root.val); if (root.right!=null){ inorderTraversal(root.right,li); } } 给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
public class Solution { /** * * @param root TreeNode类 * @return int整型ArrayList <>> */ public ArrayList > zigzagLevelOrder (TreeNode root) { // write code here ArrayList > li =new ArrayList<>(); Queue q = new LinkedList<>(); if (root!=null){ q.offer(root); } int kk=1; while(!q.isEmpty()){ int k =q.size(); ArrayList l= new ArrayList<>(); Stack s=new Stack<>(); for (int i=0;i 根据一棵树的前序遍历与中序遍历构造二叉树。
public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { return buildTree(pre,0,pre.length-1,in,0,in.length-1); } private TreeNode buildTree(int[] preorder ,int preS,int preE,int[] inorder,int inS,int inE){ if (preS>preE){ return null; } int index=0; for (int i=0;i<=inE;i++){ if (inorder[i]==preorder[preS]){ index = i; break; } } int size = index-inS; TreeNode root = new TreeNode(preorder[preS]); root.left=buildTree(preorder,preS+1,preS+size,inorder,inS,index-1); root.right=buildTree(preorder,preS+size+1,preE,inorder,index+1,inE); return root; }} 给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树
class Solution { public TreeNode sortedArrayToBST(int[] nums) { return insertInto(nums,0,nums.length-1); } private TreeNode insertInto(int[] nums,int s,int e){ if (s>e){ return null; } int mid = (e+s)/2; TreeNode root =new TreeNode(nums[mid]); root.left=insertInto(nums,s,mid-1); root.right=insertInto(nums,mid+1,e); return root; }} 翻转一棵二叉树。
class Solution { public TreeNode invertTree(TreeNode root) { return exch(root); } private TreeNode exch(TreeNode root){ if (root==null){ return null; } root.left= exch(root.left); root.right=exch(root.right); TreeNode r=root.left; root.left =root.right; root.right =r; return root; }} 给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。Class Solution{ public void flatten(TreeNode root){ if (root ==null){ return;} flatten(root.left); flatten(root.right); TreeNode left =root.left; TreeNode right =root.right; root.right=left; root.left=null; TreeNode p=new TreeNode(); While(p.right!=null){ p=p.right;} p.right=right;}} 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件： 节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。
Class Solution{ int sum=0; public TreeNode convertBST(TreeNode root){ if (root==null){ return null; } convertBST(root.right); sum=sum+root.val; root.val=sum; convertBST(root.left); return root; }} 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
class Solution { int max=0; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return max; } private int dfs(TreeNode root){ if (root == null){ return 0; } int leftmax = dfs(root.left); int rightmax =dfs(root.right); if(max 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1==null&&root2==null){ return null; } if (root1==null&&root2!=null){ return root2; } if (root1!=null&&root2==null){ return root1; } TreeNode root = new TreeNode(); root.val=root1.val+root2.val; TreeNode left =mergeTrees(root1.left,root2.left); TreeNode right =mergeTrees(root1.right,root2.right); root.left = left; root.right = right; return root; }} 转载地址：http://xoqzi.baihongyu.com/