LeetCode Tree系列一

Tree

LeetCode分组中94、95、96、98、99、100、101、102、103、104题汇总

94. Binary Tree Inorder Traversal (Medium)

题意

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:

Given binary tree [1,null,2,3],

1

      \

      2

      /

3

return [1,3,2].

二叉树的中序遍历

解题

用递归的方式很容易,这里用栈来解题,用堆栈实现中序

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> s = new Stack();
        while(root != null || !s.isEmpty()){
            while(root != null){
                s.push(root);
                root = root.left;
            }
            root = s.pop();
            ret.add(root.val);
            root = root.right;
        }
        return ret;
    }
}    

95. Unique Binary Search Trees II (Medium)

题意

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

给一个数字,将1到n构成所有满足二叉搜索树结构的二叉树

解题

用递归

public class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n == 0) return new LinkedList<>(); 
        return generateTrees(1, n);
    }
    private List<TreeNode> generateTrees(int start, int end){
        List<TreeNode> ret = new LinkedList<>();
        if(start > end) {
            ret.add(null);
            return ret;
        }
        for(int i = start; i <= end; i++){
            List<TreeNode> lefts = generateTrees(start, i - 1);
            List<TreeNode> rights = generateTrees(i + 1, end);
            for(TreeNode left : lefts){
                for(TreeNode right : rights){
                    TreeNode t = new TreeNode(i);
                    t.left = left;
                    t.right = right;
                    ret.add(t);
                   }
            }
        }
        return ret;
    }
}

96. Unique Binary Search Trees (Medium)

题意

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

给一个数字n,用1到n构成二叉搜索树,一共可以构成多少种不同结构的二叉搜索树

解题

在1到n中,我们可以使用任意一个数为根结点,n等于零时,只能有一种就是空树,当n等于1时,也只有一种结构,于是从零开始的次数分别为1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862……,这其实就是卡特兰数,求解某一个卡特兰数的方法为:G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)

public class Solution {
    public int numTrees(int n) {
        int[] nums = new int[n + 1];
        nums[0] = 1;
        nums[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                nums[i] += nums[j - 1] * nums[i - j];
            }
        }
        return nums[n];
    }
}

98. Validate Binary Search Tree (Medium)

题意

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.

The right subtree of a node contains only nodes with keys greater than the node’s key.

Both the left and right subtrees must also be binary search trees.

验证一个二叉树是否为二叉搜索树

解题

任意一个结点的左孩子小于父节点,右孩子大于父节点

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}

99. Recover Binary Search Tree (Hard)

题意

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.

交换一个二叉搜索树中的任意两个结点的值,要求我们把二叉树恢复到正确的状态

解题

利用中序遍历的性质,一个二叉搜索树的中序遍历,在局部一定是有序的,因此我们可以分别找出两个交换了的数,然后交换它们的值

public class Solution {
    private TreeNode first;
    private TreeNode second;
    private TreeNode pre = new TreeNode(Integer.MIN_VALUE);
    public void recoverTree(TreeNode root) {
        inOrder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    private void inOrder(TreeNode t){
        if(t == null) return;
        inOrder(t.left);
        if(first == null && pre.val >= t.val)
            first = pre;
        if(first != null && pre.val >= t.val)
            second = t;
        pre = t;
        inOrder(t.right);
    }
}

100. Same Tree (Easy)

题意

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

判断两颗二叉树是否相同,要相同,结构要相同,每个结点的值也要相等

解题

用递归,方法很简单

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null || q == null) {
            if(p == null && q == null) return true;
            return false;
        }
        if(p.val == q.val) return (isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) ;
        return false;
    }
}

101. Symmetric Tree (Easy)

题意

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

判断一棵树是否是以根结点堆成的

解题

用递归,先判断根结点,然后判断左子树的左孩子是否和右子树的右孩子,还需判断左子树的右孩子是否和右子树的左孩子是否满足条件

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode left, TreeNode right){
        if(left == null || right == null) return left == right;
        else if(left.val == right.val) return (isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left));
        return false;
    }
}

102. Binary Tree Level Order Traversal (Medium)

题意

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:

Given binary tree [3,9,20,null,null,15,7],

  3

/ \

   9      20

     /  \

    15   7

return its level order traversal as:

[

[3],

[9,20],

[15,7]

]

二叉树的层次遍历

解题

层次遍历需要用到队列,如果是直接线性输出的话,这道题很简单,但是这道题需要将每一层也区分开,所有用到了两个队列:

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

103. Binary Tree Zigzag Level Order Traversal

题意

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

二叉树的层次Z型遍历,在102的基础上,每一层的输出次序会调转

解题

判断层次的奇偶,从零开始,偶数就正序,奇数就逆序,在102的基础上,加入List时,偶数加在尾部,奇数加在首部

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> levelQueue = new LinkedList<>();
        if(root != null) queue.offer(root);
        int i = 0;
        while(!queue.isEmpty()){
            while(!queue.isEmpty())
                levelQueue.offer(queue.poll());
            list = new LinkedList<>();
            while(!levelQueue.isEmpty()){
                root = levelQueue.poll();
                if(i % 2 == 0){
                    list.add(root.val);
                }else {
                    list.add(0, root.val);
                }
                if(root.left != null) queue.offer(root.left);
                if(root.right != null) queue.offer(root.right);
            }
            ret.add(list);
            i++;
        }
        return ret;
    }
}

104. Maximum Depth of Binary Tree (Easy)

题意

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

求二叉树的深度,也就是二叉树中叶结点层次最深的层数

解题

递归求出左子树和右子树的高度,然后选择最大的深度

public class Solution {
    public int maxDepth(TreeNode root) {
        int rightDepth;
        int leftDepth;
        int maxDepth;
        if(root == null) return 0;
        leftDepth = maxDepth(root.left);
        rightDepth = maxDepth(root.right);
        maxDepth = Math.max(leftDepth, rightDepth);
        return maxDepth + 1;
    }
}
坚持原创分享,您的支持将鼓励我不断前行!