LeetCode刷题之树

关于二叉树的题，几乎都会用到递归的解法来做。

树用到节点TreeNode类：

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7

返回它的最大深度 3 。

题解：

class Solution {
     /**
     * 节点为空时说明高度为 0，所以返回 0；节点不为空时则分别求左右子树的高度的最大值，同时加1表示当前节点的高度，返回该数值
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        //如果当前节点为空，则返回0
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);  //递归调用获取左子节点的高度
            int rightHeight = maxDepth(root.right);  //递归调用右子节点的高度
            return Math.max(leftHeight, rightHeight) + 1; //最终返回左、右子节点最大高度加上当前节点的1
        }
    }
}

二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

题解：

class Solution {
    public int minDepth(TreeNode root) {
        //思路：得到树的最底层的叶子节点，即左右节点都为null，设置深度为1，从下往上找
        //当前节点深度为取左右节点的深度较小值，+1，即当前节点最小深度作为函数返回值，该函数为递归调用函数
        if(root == null) {
            return 0;
        }

        if(root.left == null && root.right == null) {
            return 1;
        }

        int mindepth = Integer.MAX_VALUE;
        if(root.left != null) {
            //左子节点不为空，得到左子节点的深度
            mindepth = Math.min(minDepth(root.left), mindepth);
        }
        if(root.right != null) {
            //右子节点不为空，得到右子节点的深度
            mindepth = Math.min(minDepth(root.right), mindepth);
        }
        return mindepth+1;
    }

}

226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：
4
/
2 7
/ \ /
1 3 6 9

输出：
4
/
7 2
/ \ /
9 6 3 1

题解：

class Solution {
     /**
     * 思路：
     * 观察可得翻转二叉树就是将所有节点的左右子节点调换顺序，需要使用递归
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        //将左右节点调换顺序，然后分别将左、右节点递归调用翻转的方法
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = temp;
        invertTree(root.left);
        invertTree(root.right);

        return root;  //最终需要返回根节点
    }
}

617. 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

题解：

class Solution {
    /**
     * 思路：
     * 将t2中的值往t1中合并，如果t1中节点为空，则返回t2中的值，否则返回2个节点中值的和
     * 然后递归调用方法，将t1左节点和t2左节点合并，将t1右节点和t2右节点合并
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null || t2 == null) {
            return t1 == null ? t2 : t1;
        }

        t1.val = t1.val + t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}

589. N叉树的前序遍历

给定一个 N 叉树，返回其节点值的前序遍历。

例如，给定一个 3叉树 :

返回其前序遍历: [1,3,5,6,2,4]。

题解：

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {

    /**
     * 思路：
     * 添加当前节点，遍历子节点，将每个子节点递归调用先序遍历，完成将所有选序遍历
     * @param root
     * @return
     */
    public List<Integer> res = new ArrayList<Integer>();
    public List<Integer> preorder(Node root) {
        if(root == null)
            return res;
        res.add(root.val);
        for(Node child : root.children){
            preorder(child);
        }
        return res;
    }
}

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。

题解：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> datas = new ArrayList<>();
        inOrder(root, datas);
        return datas;
    }

    public void inOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        //先添加左节点，再添加根节点，再添加右节点
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }

}