二叉树是树结构中的一种，有且最多只有两个子节点。这里将列举一些常见的操作及我的解法，具体介绍及题目在这LeetCode。
- 遍历
1.前序遍历
2.中序遍历
3.后序遍历
4.层序遍历 - 递归问题
1.树的深度
2.镜像树
3.是否存在跟到叶子节点的路径
4.由中序后序得出二叉树
5.由前序中序得出二叉树
6.最近父节点 - 其他
1.层级链接
遍历
遍历的方式共四种，除了常见的前序、中序、后序的三种外，这里还增加了层序遍历。
前序遍历：中左右
中序遍历：左中右
后序遍历：左右中
可以看出前、中、后表示的是父节点所在的位置。
层序遍历则是一层一层由左至右遍历。
前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> list=new ArrayList<Integer>();
if(root==null){
return list;
}
list.add(root.val);
list.addAll(preorderTraversal(root.left));
list.addAll(preorderTraversal(root.right));
return list;
}
中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> list=new ArrayList<Integer>();
if(root==null){
return list;
}
list.addAll(inorderTraversal(root.left));
list.add(root.val);
list.addAll(inorderTraversal(root.right));
return list;
}
后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> list=new ArrayList<Integer>();
if(root==null){
return list;
}
list.addAll(postorderTraversal(root.left));
list.addAll(postorderTraversal(root.right));
list.add(root.val);
return list;
}
层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
ArrayList<Integer> levelList=new ArrayList<Integer>();
ArrayList<List<Integer>> list=new ArrayList<List<Integer>>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
for(int i=0;i<size;i++){
TreeNode node=queue.poll();
if(node==null) continue;
levelList.add(node.val);
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
if(i==size-1){
list.add(levelList);
levelList=new ArrayList<Integer>();
}
}
}
return list;
}
递归问题
树的深度
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
int l=maxDepth(root.left);
int r=maxDepth(root.right);
return l>r?l+1:r+1;
}
镜像树
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return st(root.left,root.right);
}
public boolean st(TreeNode lNode,TreeNode rNode){
if(lNode==null&&rNode==null){
return true;
}else if(lNode!=null&&rNode!=null){
return (lNode.val==rNode.val) && st(lNode.left,rNode.right) && st(lNode.right,rNode.left);
}else{
return false;
}
}
是否存在跟到叶子节点的路径(我认为这种翻译比较合适)
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null){
return false;
}
if(root.left==null&&root.right==null&&root.val==sum){
return true;
}
return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
}
由中序后序得出二叉树
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(postorder.length<1){
return null;
}
TreeNode root=new TreeNode(postorder[postorder.length-1]);
int position=0;
for(int i=0;i<inorder.length;i++){
if(root.val==inorder[i]){
position=i;
break;
}
}
int[] inorderL=new int[position];
int[] inorderR=new int[inorder.length-1-position];
int[] postorderL=new int[position];
int[] postorderR=new int[inorder.length-1-position];
System.arraycopy(inorder,0,inorderL,0,position);
System.arraycopy(inorder,position+1,inorderR,0,inorder.length-1-position);
System.arraycopy(postorder,0,postorderL,0,position);
System.arraycopy(postorder,position,postorderR,0,inorder.length-1-position);
root.left=buildTree(inorderL,postorderL);
root.right=buildTree(inorderR,postorderR);
return root;
}
由前序中序得出二叉树
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length<1){
return null;
}
TreeNode root=new TreeNode(preorder[0]);
int position=0;
for(int i=0;i<inorder.length;i++){
if(root.val==inorder[i]){
position=i;
break;
}
}
int[] inorderL=new int[position];
int[] inorderR=new int[inorder.length-1-position];
int[] preorderL=new int[position];
int[] preorderR=new int[inorder.length-1-position];
System.arraycopy(inorder,0,inorderL,0,position);
System.arraycopy(inorder,position+1,inorderR,0,inorder.length-1-position);
System.arraycopy(preorder,1,preorderL,0,position);
System.arraycopy(preorder,position+1,preorderR,0,inorder.length-1-position);
root.left=buildTree(preorderL,inorderL);
root.right=buildTree(preorderR,inorderR);
return root;
}
最近父节点
private TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (root.val == p.val) return p;
if (root.val == q.val) return q;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
其他
层级链接
private void connect(TreeLinkNode root) {
LinkedList<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeLinkNode node = queue.poll();
if (i == size - 1) {
node.next = null;
} else {
node.next = queue.peek();
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
由于具体的题目都在LeetCode，所以这里只给贴出了解决方案。具体的代码
网友评论