二叉树相关OJ题

1. 检查两颗树是否相同

OJ链接

    public boolean isSameTree(TreeNode p, TreeNode q) {
        //先判断结构是否一致
        if(p == null && q != null || p != null && q == null) {
            return false;
        }
        //此时要么都为空，要么都不为空
        if(p == null && q == null) {
            return true;
        }
        //此时都不为空 判断值是否相同
        if(p.val != q.val) {
            return false;
        }
        //都不为空，且值相同
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

2. 另一颗树的子树

OJ链接

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) {
            return false;
        }
        //判断当前子树和根节点是否相同
        if(isSameTree(root,subRoot)) return true;
        //判断子树和当前root的左子树是否一样
        if(isSubtree(root.left,subRoot)) return true;
        //判断子树和当前root的右子树是否一样
        if(isSubtree(root.right,subRoot)) return true;
        return false;
    }
    public boolean isSameTree(TreeNode p,TreeNode q) {
        if(p == null && q == null) {
            return true;
        }
        //判断结构是否相同
        if(p == null && q != null || p != null && q == null) {
            return false;
        }
        //都不为空，判断值是否相同
        if(p.val != q.val) {
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

3. 翻转二叉树

OJ链接

​

    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        //当节点的左右子树都为null，则没有必要交换，直接返回该节点即可
        if(root.left == null && root.right == null) {
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

4. 判断一颗二叉树是否是平衡二叉树

OJ链接

​

    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        return getHeight(root) >= 0;
    }
    public int getHeight(TreeNode root) {
        if(root == null) return 0;
        int leftHeight = getHeight(root.left);
        if(leftHeight < 0) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if(rightHeight != -1 && Math.abs(leftHeight - rightHeight) <= 1) {
            return Math.max(leftHeight,rightHeight) + 1;
        }else {
            return -1;
        }
    }

5. 对称二叉树

OJ链接

    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        if(leftTree == null && rightTree != null 
            ||leftTree != null && rightTree == null) {
                return false;
        }
        if(leftTree == null && rightTree == null) {
            return true;
        }
        if(leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right) 
                && isSymmetricChild(leftTree.right,rightTree.left);
    }

6. 二叉树的构建及遍历

OJ链接

import java.util.Scanner;

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;
    public TreeNode(char val){
        this.val = val;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inOrderTree(root);
        }

    }
    public static int i = 0;
    public static TreeNode createTree(String str) {
        TreeNode root = null;
        if(str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }

    public static void inOrderTree(TreeNode root) {
        if(root == null) return;
        inOrderTree(root.left);
        System.out.print(root.val + " ");
        inOrderTree(root.right);
    }
}

7. 二叉树的分层遍历 

OJ链接

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list0 = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                list0.add(cur.val);
                size--;
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(list0);
        }
        return list;
    }
}

8. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 

OJ链接

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(p == root || q == root) return root;
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(leftTree != null && rightTree != null) {
            //p、q分别在跟的左右两边
            return root;
        }else if(leftTree != null) {
            //p、q都在左边
            return leftTree;
        }else {
            //p、q都在右边
            return rightTree;
        }
    }

9. 根据一棵树的前序遍历与中序遍历构造二叉树

OJ链接

class Solution {
    public int preIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,preorder.length-1);
    }
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
        preIndex++;
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    private int findIndex(int[] inorder,int inbegin,int inend,int val) {
        for(int i = inbegin;i <= inend;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}

10. 根据一棵树的中序遍历与后序遍历构造二叉树

OJ链接

class Solution {
    public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild(inorder,postorder,0,postIndex);
    }
    public TreeNode buildTreeChild(int[] inorder,int[] postorder,int inBegin,int inEnd) {
        if(inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findVal(inorder,inBegin,inEnd,postorder[postIndex]);
        postIndex--;
        root.right = buildTreeChild(inorder,postorder,rootIndex+1,inEnd);
        root.left = buildTreeChild(inorder,postorder,inBegin,rootIndex-1);
        return root;
    }
    private int findVal(int[] inorder,int inBegin,int inEnd,int val) {
        for(int i = inBegin; i <= inEnd;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}

11. 二叉树创建字符串

OJ链接

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder sbd = new StringBuilder();
        tree2strChild(root,sbd);
        return sbd.toString();
    }
    public void tree2strChild(TreeNode root,StringBuilder sbd) {
        if(root == null) return;
        sbd.append(root.val);
        if(root.left != null) {
            sbd.append("(");
            tree2strChild(root.left,sbd);
            sbd.append(")");
        }else {
            if(root.right == null) {
                return;
            }else {
                sbd.append("()");
            }
        }
        if(root.right != null) {
            sbd.append("(");
            tree2strChild(root.right,sbd);
            sbd.append(")");
        }else {
            return;
        }
    }
}

12. 二叉树前序非递归遍历实现

OJ链接

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while( cur != null || !stack.isEmpty()) {
            while( cur != null) {
                res.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return res;
    }
}

13. 二叉树中序非递归遍历实现

OJ链接

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new Stack<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return list;
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }
}

14. 二叉树后序非递归遍历实现

OJ链接

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev) {
                list.add(top.val);
                prev = top;
                stack.pop();
            }else {
                cur = top.right;
            }
        }
        return list;
    }
}